题目描述
leetcode 困难题
给你数字字符串 s ，请你返回 s 中长度为 5 的 回文子序列 数目。由于答案可能很大，请你将答案对 $10^9 + 7$ 取余 后返回。
提示：
如果一个字符串从前往后和从后往前读相同，那么它是 回文字符串 。
子序列是一个字符串中删除若干个字符后，不改变字符顺序，剩余字符构成的字符串。
示例1：
1
2
3
4
5
| 输入：s = "103301"
输出：2
解释：
总共有 6 长度为 5 的子序列："10330" ，"10331" ，"10301" ，"10301" ，"13301" ，"03301" 。
它们中有两个（都是 "10301"）是回文的。
|
提示1：
1
2
| 1 <= s.length <= 10^4
s 只包含数字字符。
|
枚举
由于题目要求的子序列限定了长度必须为 $5$，那么我们可以通过枚举回文子序列的中心点来得出结果。
因为 $s$ 只包含数字字符，可知中心点的每侧字符只有 $10 \times 10$ 种可能（如果只包含字母的话就是 $24 \times 24$ 种可能），那么我们可以通过类似前缀和的方式进行枚举即可得到结果。
具体来说，我们预先通过一个 $right[10][10]$ 保存该数组所有长度为 $2$ 的子序列组合的个数、$rightCount[10]$ 保存每个不同字符的出现个数。然后 $i$ 从 $0$ 开始遍历，每次将当前字符的可能性从 $right[10][10]$ 和 $right[10]$ 中撤销，并累加到 $left[10][10]$ 和 $leftCount$ 中，再遍历所有 $left[10][10]$ ，那么通过乘法原理可知，以当前字符为中心的回文子序列个数就为每个 $left[a][b] \times right[b][a]$ 的总和。
题目给出 $n$ 范围为 $10^4$，内层最多循环 $10 \times 10$ 次，计算量为 $10^6$ ，不会 TLE。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| class Solution {
static int MOD = (int)(1e9 + 7);
public int countPalindromes(String s) {
int n = s.length();
int[][] right = new int[10][10];
int[] rightCount = new int[10];
for(int i = n - 1; i >= 0; i--){
for(int j = 0; j <= 9; j++){
right[s.charAt(i) - '0'][j] += rightCount[j];
}
rightCount[s.charAt(i) - '0']++;
}
int[][] left = new int[10][10];
int[] leftCount = new int[10];
long ans = 0;
for(int i = 0; i < n; i++){
char item = s.charAt(i);
rightCount[item - '0']--;
for(int j = 0; j <= 9; j++){
right[item - '0'][j] -= rightCount[j];
}
for(int a = 0; a <= 9; a++){
for(int b = 0; b <= 9; b++){
long temp = ans;
ans = (ans % MOD + ((long)left[a][b] * right[b][a]) % MOD) % MOD;
}
}
for(int j = 0; j <= 9; j++){
left[j][item - '0'] += leftCount[j];
}
leftCount[item - '0']++;
}
return (int)(ans % MOD);
}
}
|
枚举 + 动态规划
另一种做法是枚举出长度为 $5$ 的回文串的所有可能，再将字符串中这些回文子序列出现的次数累加起来就是答案。
枚举出所有回文串需要循环 $10 \times 10 \times 10$ 次，求子序列出现次数计算量为 $5 \times 10^4$，总计算量为 $5 \times 10^7$ ，不会 TLE。
LC-115：枚举某个子序列在字符串中出现次数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| class Solution {
static int MOD = (int)(1e9 + 7);
public int countPalindromes(String s) {
long ans = 0;
for(int i = 0; i <= 9; i++){
for(int j = 0; j <= 9; j++){
for(int k = 0; k <= 9; k++){
StringBuilder sb = new StringBuilder().append(i).append(j).append(k).append(j).append(i);
ans = (ans + help(s, sb.toString())) % MOD;
}
}
}
return (int)(ans % MOD);
}
private long help(String s, String t){
int n = s.length();
int m = t.length();
long[][] dp = new long[n + 1][m + 1];
for(int i = 0; i <= n; i++){
dp[i][0] = 1;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
dp[i][j] = dp[i - 1][j];
if(s.charAt(i - 1) == t.charAt(j - 1)){
dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % MOD;
}
}
}
return dp[n][m];
}
}
|