Python描述 LeetCode 730. 统计不同回文子序列
发布时间：2023-08-12 18:08:21 184 相关标签：
Python描述 LeetCode 730. 统计不同回文子序列
题目
给定一个字符串 s，返回 s 中不同的非空「回文子序列」个数 。
通过从 s 中删除 0 个或多个字符来获得子序列。
如果一个字符序列与它反转后的字符序列一致，那么它是「回文字符序列」。
如果有某个 i , 满足 ai != bi ，则两个序列 a1, a2, ... 和 b1, b2, ... 不同。
注意：
- 结果可能很大，你需要对
109 + 7 取模 。
示例 1：
输入：s = 'bccb'
输出：6
解释：6 个不同的非空回文子字符序列分别为：'b', 'c', 'bb', 'cc', 'bcb', 'bccb'。
注意：'bcb' 虽然出现两次但仅计数一次。
示例 2：
输入：s = 'abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba'
输出：104860361
解释：共有 3104860382 个不同的非空回文子序列，104860361 对 109 + 7 取模后的值。
提示：
-
1 <= s.length <= 1000
-
s[i] 仅包含'a','b','c' 或'd'
解题思路
动态规划。dp[char][i][j]表示s[i:j+1]中可以删除任意字符组成两端为char的回文子串数量
转移方程：
1. char == s[i] == s[j]：两端的字符都是char，则这两个字符本身就可以组成(char)和(char char)两个回文子串，其次在s[i+1:j]中所有的回文子串加上两端的char都是回文子串，即dp[char][i][j] = sum(item[i+1][j-1] for item in dp)
2. s[i] != s[j] and char == s[i]: 右端字符不是char，直接删除该字符，dp[char][i][j] = dp[char][i][j-1]
3. s[i] != s[j] and char == s[j]: 左端字符不是char，直接删除该字符，dp[char][i][j] = dp[char][i+1][j]
4. s[i] != s[j] and char != s[i] and char != s[j]: 两端都不是该字符，两端都删除,dp[char][i][j] = dp[char][i+1][j-1]
Python描述
class Solution:
def countPalindromicSubsequences(self, s: str) -> int:
MOD = 10**9 + 7
n = len(s)
# dp[char][i][j]: s[i:j+1]可以删成两端为char的回文子串数量
dp = [[[0 for i in range(n)] for j in range(n)] for _ in range(4)]
# 初始化：长度为1时，可以构成一个回文子串
for idx,ch in enumerate("abcd"):
for i in range(n):
if ch == s[i]:
dp[idx][i][i] = 1
# 子串长度：2 - n
for length in range(2,n+1):
for j in range(length-1,n):
i = j - length + 1
for idx,ch in enumerate("abcd"):
if ch == s[i] == s[j]:
dp[idx][i][j] = 2 + sum(item[i+1][j-1] for item in dp)
elif ch == s[i]:
dp[idx][i][j] = dp[idx][i][j-1]
elif ch == s[j]:
dp[idx][i][j] = dp[idx][i+1][j]
else:
dp[idx][i][j] = dp[idx][i+1][j-1]
res = sum([item[0][n-1] for item in dp]) % MOD
return
文章来源： https://blog.51cto.com/u_15845758/5795762
特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。
举报
