2484. 统计回文子序列数目
给你数字字符串 s
,请你返回 s
中长度为 5
的 回文子序列 数目。由于答案可能很大,请你将答案对 10^9 + 7
取余 后返回。
提示:
示例 1:
```txt
输入:s = "103301"
输出:2
解释:
总共有 6 长度为 5 的子序列:"10330" ,"10331" ,"10301" ,"10301" ,"13301" ,"03301" 。
它们中有两个(都是 "10301")是回文的。
```
示例 2:
```txt
输入:s = "0000000"
输出:21
解释:所有 21 个长度为 5 的子序列都是 "00000" ,都是回文的。
```
示例 3:
```txt
输入:s = "9999900000"
输出:2
解释:仅有的两个回文子序列是 "99999" 和 "00000" 。
```
提示:
">
题目
2484. 统计回文子序列数目
给你数字字符串 s
,请你返回 s
中长度为 5
的 回文子序列 数目。由于答案可能很大,请你将答案对 10^9 + 7
取余 后返回。
提示:
- 如果一个字符串从前往后和从后往前读相同,那么它是 回文字符串 。
- 子序列是一个字符串中删除若干个字符后,不改变字符顺序,剩余字符构成的字符串。
示例 1:
1 2 3 4 5
| 输入:s = "103301" 输出:2 解释: 总共有 6 长度为 5 的子序列:"10330" ,"10331" ,"10301" ,"10301" ,"13301" ,"03301" 。 它们中有两个(都是 "10301")是回文的。
|
示例 2:
1 2 3
| 输入:s = "0000000" 输出:21 解释:所有 21 个长度为 5 的子序列都是 "00000" ,都是回文的。
|
示例 3:
1 2 3
| 输入:s = "9999900000" 输出:2 解释:仅有的两个回文子序列是 "99999" 和 "00000" 。
|
提示:
-
1 <= s.length <= 10^4
s
只包含数字字符。
题解
方法一:
思路
两次dp,枚举分割线。
设p[i][j][k]
为前i位以j和k结尾的子序列个数, s[i][j][k]
为后i位以j和k结尾的子序列个数。
这时答案为
总时间复杂度,字符集大小不超过10,为字符串长度
代码
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 37 38 39 40 41 42 43 44
| class Solution { public: using ll = long long; const ll M = 1e9+7; ll pcnt[10], scnt[10]; ll pdp[10005][10][10], sdp[10005][10][10]; int countPalindromes(string s) { int n = s.size(); for (int i=0; i<n; i++) { int u = s[i]-'0'; pcnt[u]++; for (int j=0; j<10; j++) { for (int k=0; k<10; k++) { if (i>0) pdp[i][j][k] = pdp[i-1][j][k]; if (i>0 && u == k) pdp[i][j][k] += pcnt[j] + (k==j?-1:0); pdp[i][j][k]%=M; } } } for (int i=n-1; i>=0; i--) { int u = s[i] - '0'; scnt[u]++; for (int j=0; j<10; j++) { for (int k=0; k<10; k++) { if (i<n-1) sdp[i][j][k] = sdp[i+1][j][k]; if (i<n-1 && u == j) sdp[i][j][k] += scnt[k] + (k==j?-1:0); pdp[i][j][k]%=M; } } } ll ans = 0; for (int i=2; i<n-2; i++) { for (int j=0; j<10; j++) { for (int k=0; k<10; k++) { ans += pdp[i-1][j][k]*sdp[i+1][k][j]; ans %= M; } } } return ans; } };
|