class Solution {
public:
int countPalindromes(string s) {
}
};
2484. 统计回文子序列数目
给你数字字符串 s ，请你返回 s 中长度为 5 的 回文子序列 数目。由于答案可能很大，请你将答案对 109 + 7 取余 后返回。
提示：
示例 1：
输入：s = "103301" 输出：2 解释： 总共有 6 长度为 5 的子序列："10330" ，"10331" ，"10301" ，"10301" ，"13301" ，"03301" 。 它们中有两个（都是 "10301"）是回文的。
示例 2：
输入：s = "0000000" 输出：21 解释：所有 21 个长度为 5 的子序列都是 "00000" ，都是回文的。
示例 3：
输入：s = "9999900000" 输出：2 解释：仅有的两个回文子序列是 "99999" 和 "00000" 。
提示：
1 <= s.length <= 104s 只包含数字字符。原站题解
golang 解法, 执行用时: 8 ms, 内存消耗: 1.9 MB, 提交时间: 2022-12-14 11:46:34
func countPalindromes(s string) (ans int) {
const mod int = 1e9 + 7
n := len(s)
suf := [10]int{}
suf2 := [10][10]int{}
for i := n - 1; i >= 0; i-- {
d := s[i] - '0'
for j, c := range suf {
suf2[d][j] += c
}
suf[d]++
}
pre := [10]int{}
pre2 := [10][10]int{}
for _, d := range s[:n-1] {
d -= '0'
suf[d]--
for j, c := range suf {
suf2[d][j] -= c // 撤销
}
for j, sf := range suf2 {
for k, c := range sf {
ans += pre2[j][k] * c // 枚举所有字符组合
}
}
for j, c := range pre {
pre2[d][j] += c
}
pre[d]++
}
return ans % mod
}
java 解法, 执行用时: 7 ms, 内存消耗: 39.4 MB, 提交时间: 2022-12-14 11:46:20
class Solution {
private static final long MOD = (long) 1e9 + 7;
public int countPalindromes(String S) {
var s = S.toCharArray();
int[] pre = new int[10], suf = new int[10];
int[][] pre2 = new int[10][10], suf2 = new int[10][10];
for (var i = s.length - 1; i >= 0; --i) {
var d = s[i] - '0';
for (var j = 0; j < 10; ++j)
suf2[d][j] += suf[j];
++suf[d];
}
var ans = 0L;
for (var d : s) {
d -= '0';
--suf[d];
for (var j = 0; j < 10; ++j)
suf2[d][j] -= suf[j]; // 撤销
for (var j = 0; j < 10; ++j)
for (var k = 0; k < 10; ++k)
ans += (long) pre2[j][k] * suf2[j][k]; // 枚举所有字符组合
for (var j = 0; j < 10; ++j)
pre2[d][j] += pre[j];
++pre[d];
}
return (int) (ans % MOD);
}
}
python3 解法, 执行用时: 348 ms, 内存消耗: 15 MB, 提交时间: 2022-12-14 11:45:45
class Solution:
def countPalindromes(self, s: str) -> int:
suf = [0] * 10
suf2 = [0] * 100
for d in map(int, reversed(s)):
for j, c in enumerate(suf):
suf2[d * 10 + j] += c
suf[d] += 1
ans = 0
pre = [0] * 10
pre2 = [0] * 100
for d in map(int, s):
suf[d] -= 1
for j, c in enumerate(suf):
suf2[d * 10 + j] -= c # 撤销
ans += sum(c1 * c2 for c1, c2 in zip(pre2, suf2)) # 枚举所有字符组合
for j, c in enumerate(pre):
pre2[d * 10 + j] += c
pre[d] += 1
return ans % (10 ** 9 + 7)