LeetCode 题解工作台
统计不同回文子序列
给你一个字符串 s ，返回 s 中不同的非空回文子序列个数 。由于答案可能很大，请返回对 10 9 + 7 取余 的结果。 字符串的子序列可以经由字符串删除 0 个或多个字符获得。 如果一个序列与它反转后的序列一致，那么它是回文序列。 如果存在某个 i , 满足 a i != b i ，则两个序列 …
2
题型
4
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
class Solution: def countPalindromicSubsequences(self, s: str) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个字符串 s ，返回 s 中不同的非空回文子序列个数 。由于答案可能很大，请返回对 109 + 7 取余 的结果。
字符串的子序列可以经由字符串删除 0 个或多个字符获得。
如果一个序列与它反转后的序列一致，那么它是回文序列。
如果存在某个 i , 满足 ai != bi ，则两个序列 a1, a2, ... 和 b1, b2, ... 不同。
示例 1：
输入：s = 'bccb' 输出：6 解释：6 个不同的非空回文子字符序列分别为：'b', 'c', 'bb', 'cc', 'bcb', 'bccb'。 注意：'bcb' 虽然出现两次但仅计数一次。
示例 2：
输入：s = 'abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba' 输出：104860361 解释：共有 3104860382 个不同的非空回文子序列，104860361 是对 109 + 7 取余后的值。
提示：
1 <= s.length <= 1000s[i]仅包含'a','b','c'或'd'
解题思路
方法一：区间 DP
class Solution:
def countPalindromicSubsequences(self, s: str) -> int:
mod = 10**9 + 7
n = len(s)
dp = [[[0] * 4 for _ in range(n)] for _ in range(n)]
for i, c in enumerate(s):
dp[i][i][ord(c) - ord('a')] = 1
for l in range(2, n + 1):
for i in range(n - l + 1):
j = i + l - 1
for c in 'abcd':
k = ord(c) - ord('a')
if s[i] == s[j] == c:
dp[i][j][k] = 2 + sum(dp[i + 1][j - 1])
elif s[i] == c:
dp[i][j][k] = dp[i][j - 1][k]
elif s[j] == c:
dp[i][j][k] = dp[i + 1][j][k]
else:
dp[i][j][k] = dp[i + 1][j - 1][k]
return sum(dp[0][-1]) % mod
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on the final approach but generally involves O(n^2) due to the nested loop over substring ranges. Space complexity also depends on the approach, but a 2D table to store dp values will require O(n^2) space. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The candidate understands dynamic programming and is able to apply it to string problems.
- question_mark
The candidate can efficiently manage large outputs using modulo arithmetic.
- question_mark
The candidate is aware of overlapping subproblems and optimizes using memoization.
常见陷阱
外企场景- error
Failing to handle overlapping subproblems efficiently, leading to unnecessary recalculations.
- error
Forgetting to apply the modulo operation, causing overflow or incorrect results.
- error
Overcomplicating the problem, missing simpler dynamic programming solutions with manageable time complexity.
进阶变体
外企场景- arrow_right_alt
Consider if the string has repeated characters and how that affects the number of unique subsequences.
- arrow_right_alt
What happens if the input string contains only one character?
- arrow_right_alt
Explore optimization techniques if the string length is increased significantly.