LeetCode 题解工作台
统计回文子序列数目
给你数字字符串 s ，请你返回 s 中长度为 5 的 回文子序列 数目。由于答案可能很大，请你将答案对 10 9 + 7 取余 后返回。 提示： 如果一个字符串从前往后和从后往前读相同，那么它是 回文字符串 。 子序列是一个字符串中删除若干个字符后，不改变字符顺序，剩余字符构成的字符串。 示例 1：…
2
题型
4
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
时间复杂度 $O(100 \times n)$，空间复杂度 $O(100 \times n)$。其中 为字符串 的长度。 class Solution:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你数字字符串 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只包含数字字符。
解题思路
方法一：枚举 + 计数
时间复杂度 ，空间复杂度 。其中 为字符串 的长度。
class Solution:
def countPalindromes(self, s: str) -> int:
mod = 10**9 + 7
n = len(s)
pre = [[[0] * 10 for _ in range(10)] for _ in range(n + 2)]
suf = [[[0] * 10 for _ in range(10)] for _ in range(n + 2)]
t = list(map(int, s))
c = [0] * 10
for i, v in enumerate(t, 1):
for j in range(10):
for k in range(10):
pre[i][j][k] = pre[i - 1][j][k]
for j in range(10):
pre[i][j][v] += c[j]
c[v] += 1
c = [0] * 10
for i in range(n, 0, -1):
v = t[i - 1]
for j in range(10):
for k in range(10):
suf[i][j][k] = suf[i + 1][j][k]
for j in range(10):
suf[i][j][v] += c[j]
c[v] += 1
ans = 0
for i in range(1, n + 1):
for j in range(10):
for k in range(10):
ans += pre[i - 1][j][k] * suf[i + 1][j][k]
ans %= mod
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate demonstrates strong understanding of dynamic programming and state transitions.
- question_mark
Candidate can handle modular arithmetic in large-number scenarios.
- question_mark
Candidate shows the ability to break down complex problems into manageable subproblems.
常见陷阱
外企场景- error
Not using modular arithmetic correctly can lead to overflow errors.
- error
Inefficient state transitions can make the solution too slow for large inputs.
- error
Incorrect counting of subsequences that may result in overcounting or missing valid subsequences.
进阶变体
外企场景- arrow_right_alt
Count palindromic subsequences of a different length.
- arrow_right_alt
Count palindromic subsequences of varying lengths dynamically.
- arrow_right_alt
Solve for strings that contain non-numeric characters or other constraints.