Hard
题目描述
给你一个数字字符串 s ，请你返回 s 中长度为 5 的回文子序列数目。由于答案可能很大，请你将答案对 10^9 + 7 取余后返回。
注意：
- 如果一个字符串正着读和反着读相同，那么它是回文的。
- 子序列是一个可以由其他字符串删除某些字符而不改变剩余字符顺序得到的字符串。
示例 1：
输入：s = "103301"
输出：2
解释：
长度为 5 的子序列共有 6 个："10330","10331","10301","10301","13301","03301"。
其中 2 个（都等于 "10301"）是回文的。
示例 2：
输入：s = "0000000"
输出：21
解释：所有 21 个长度为 5 的子序列都是 "00000"，都是回文的。
示例 3：
输入：s = "9999900000"
输出：2
解释：仅有的两个回文子序列是 "99999" 和 "00000"。
提示：
1 <= s.length <= 10^4s只包含数字字符。
解题思路
这道题要求统计长度为 5 的回文子序列数量。对于长度为 5 的回文串，其形式必定是 abcba，其中第 1 位和第 5 位相同，第 2 位和第 4 位相同，第 3 位可以是任意字符。
核心思路：
- 枚举每个位置作为回文串的中心（第 3 位）
- 对于每个中心位置，计算其左侧有多少种
ab的组合，右侧有多少种ba的组合 - 左右两侧的组合数相乘即为以当前位置为中心的回文子序列数
具体实现：
- 预处理：对于每个位置，计算其左侧每种数字对
(i,j)的出现次数 - 预处理：对于每个位置，计算其右侧每种数字对
(i,j)的出现次数 - 遍历每个可能的中心位置，枚举所有可能的数字对
(a,b)，将左侧ab的数量与右侧ba的数量相乘
由于数字只有 0-9，所以数字对最多有 100 种组合。时间复杂度为 O(n)，空间复杂度为 O(n)。
代码实现
class Solution {
public:
int countPalindromes(string s) {
const int MOD = 1e9 + 7;
int n = s.length();
// left[i][j][k] 表示位置 i 左侧数字 j,k 组合的数量
vector<vector<vector<int>>> left(n, vector<vector<int>>(10, vector<int>(10, 0)));
// right[i][j][k] 表示位置 i 右侧数字 j,k 组合的数量
vector<vector<vector<int>>> right(n, vector<vector<int>>(10, vector<int>(10, 0)));
// 计算每个位置左侧的数字对数量
vector<int> leftCount(10, 0);
for (int i = 0; i < n; i++) {
if (i > 0) {
for (int j = 0; j < 10; j++) {
for (int k = 0; k < 10; k++) {
left[i][j][k] = left[i-1][j][k];
}
}
}
if (i > 0) {
int digit = s[i-1] - '0';
for (int j = 0; j < 10; j++) {
left[i][j][digit] += leftCount[j];
}
leftCount[digit]++;
}
}
// 计算每个位置右侧的数字对数量
vector<int> rightCount(10, 0);
for (int i = n - 1; i >= 0; i--) {
if (i < n - 1) {
for (int j = 0; j < 10; j++) {
for (int k = 0; k < 10; k++) {
right[i][j][k] = right[i+1][j][k];
}
}
}
if (i < n - 1) {
int digit = s[i+1] - '0';
for (int j = 0; j < 10; j++) {
right[i][digit][j] += rightCount[j];
}
rightCount[digit]++;
}
}
long long result = 0;
// 枚举每个位置作为中心
for (int i = 2; i < n - 2; i++) {
for (int a = 0; a < 10; a++) {
for (int b = 0; b < 10; b++) {
result = (result + (long long)left[i][a][b] * right[i][a][b]) % MOD;
}
}
}
return result;
}
};
class Solution:
def countPalindromes(self, s: str) -> int:
MOD = 10**9 + 7
n = len(s)
# left[i][j][k] 表示位置 i 左侧数字 j,k 组合的数量
left = [[[0] * 10 for _ in range(10)] for _ in range(n)]
# right[i][j][k] 表示位置 i 右侧数字 j,k 组合的数量
right = [[[0] * 10 for _ in range(10)] for _ in range(n)]
# 计算每个位置左侧的数字对数量
left_count = [0] * 10
for i in range(n):
if i > 0:
for j in range(10):
for k in range(10):
left[i][j][k] = left[i-1][j][k]
if i > 0:
digit = int(s[i-1])
for j in range(10):
left[i][j][digit] += left_count[j]
left_count[digit] += 1
# 计算每个位置右侧的数字对数量
right_count = [0] * 10
for i in range(n-1, -1, -1):
if i < n - 1:
for j in range(10):
for k in range(10):
right[i][j][k] = right[i+1][j][k]
if i < n - 1:
digit = int(s[i+1])
for j in range(10):
right[i][digit][j] += right_count[j]
right_count[digit] += 1
result = 0
# 枚举每个位置作为中心
for i in range(2, n - 2):
for a in range(10):
for b in range(10):
result = (result + left[i][a][b] * right[i][a][b]) % MOD
return result
public class Solution {
public int CountPalindromes(string s) {
const int MOD = 1000000007;
int n = s.Length;
// left[i,j,k] 表示位置 i 左侧数字 j,k 组合的数量
int[,,] left = new int[n, 10, 10];
// right[i,j,k] 表示位置 i 右侧数字 j,k 组合的数量
int[,,] right = new int[n, 10, 10];
// 计算每个位置左侧的数字对数量
int[] leftCount = new int[10];
for (int i = 0; i < n; i++) {
if (i > 0) {
for (int j = 0; j < 10; j++) {
for (int k = 0; k < 10; k++) {
left[i, j, k] = left[i-1, j, k];
}
}
}
if (i > 0) {
int digit = s[i-1] - '0';
for (int j = 0; j < 10; j++) {
left[i, j, digit] += leftCount[j];
}
leftCount[digit]++;
}
}
// 计算每个位置右侧的数字对数量
int[] rightCount = new int[10];
for (int i = n - 1; i >= 0; i--) {
if (i < n - 1) {
for (int j = 0; j < 10; j++) {
for (int k = 0; k < 10; k++) {
right[i, j, k] = right[i+1, j, k];
}
}
}
if (i < n - 1) {
int digit = s[i+1] - '0';
for (int j = 0; j < 10; j++) {
right[i, digit, j] += rightCount[j];
}
rightCount[digit]++;
}
}
long result = 0;
// 枚举每个位置作为中心
for (int i = 2; i < n - 2; i++) {
for (int a = 0; a < 10; a++) {
for (int b = 0; b < 10; b++) {
result = (result + (long)left[i, a, b] * right[i, a, b]) % MOD;
}
}
}
return (int)result;
}
}
var countPalindromes = function(s) {
const MOD = 1e9 + 7;
const n = s.length;
// left[i][j][k] 表示位置 i 左侧数字 j,k 组合的数量
const left = Array(n).fill().map(() =>
Array(10).fill().map(() => Array(10).fill(0))
);
// right[i][j][k] 表示位置 i 右侧数字 j,k 组合的数量
const right = Array(n).fill().map(() =>
Array(10).fill().map(() => Array(10).fill(0))
);
// 计算每个位置左侧的数字对数量
const leftCount = Array(10).fill(0);
for (let i = 0; i < n; i++) {
if (i > 0) {
for (let j = 0; j < 10; j++) {
for (let k = 0; k < 10; k++) {
left[i][j][k] = left[i-1][j][k];
}
}
}
if (i > 0) {
const digit = parseInt(s[i-1]);
for (let j = 0; j < 10; j++) {
left[i][j][digit] += leftCount[j];
}
leftCount[digit]++;
}
}
// 计算每个位置右侧的数字对数量
const rightCount = Array(10).fill(0);
for (let i = n - 1; i >= 0; i--) {
if (i < n - 1) {
for (let j = 0; j < 10; j++) {
for (let k = 0; k < 10; k++) {
right[i][j][k] = right[i+1][j][k];
}
}
}
if (i < n - 1) {
const digit = parseInt(s[i+1]);
for (let j = 0; j < 10; j++) {
right[i][digit][j] += rightCount[j];
}
rightCount[digit]++;
}
}
let result = 0;
// 枚举每个位置作为中心
for (let i = 2; i < n - 2; i++) {
for (let a = 0; a < 10; a++) {
for (let b = 0; b < 10; b++) {
result = (result + left[i][a][b] * right[i][a][b]) % MOD;
}
}
}
return result;
};
复杂度分析
| 复杂度 | 大小 |
|---|---|
| 时间复杂度 | O(n) |
| 空间复杂度 | O(n) |
其中 n 是字符串长度。虽然有三重循环，但内层循环次数是常数（10×10=100），所以总时间复杂度仍为线性。