class Solution {
public:
int countPalindromicSubsequences(string s) {
}
};
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 <= 1000s[i] 仅包含 'a', 'b', 'c' 或 'd' 相似题目
原站题解
golang 解法, 执行用时: 92 ms, 内存消耗: 47 MB, 提交时间: 2023-02-26 11:45:17
func countPalindromicSubsequences(s string) (ans int) {
const mod int = 1e9 + 7
n := len(s)
dp := [4][][]int{}
for i := range dp {
dp[i] = make([][]int, n)
for j := range dp[i] {
dp[i][j] = make([]int, n)
}
}
for i, c := range s {
dp[c-'a'][i][i] = 1
}
for sz := 2; sz <= n; sz++ {
for i, j := 0, sz-1; j < n; i++ {
for k, c := 0, byte('a'); k < 4; k++ {
if s[i] == c && s[j] == c {
dp[k][i][j] = (2 + dp[0][i+1][j-1] + dp[1][i+1][j-1] + dp[2][i+1][j-1] + dp[3][i+1][j-1]) % mod
} else if s[i] == c {
dp[k][i][j] = dp[k][i][j-1]
} else if s[j] == c {
dp[k][i][j] = dp[k][i+1][j]
} else {
dp[k][i][j] = dp[k][i+1][j-1]
}
c++
}
j++
}
}
for _, d := range dp {
ans += d[0][n-1]
}
return ans % mod
}
java 解法, 执行用时: 137 ms, 内存消耗: 67.2 MB, 提交时间: 2023-02-26 11:44:46
class Solution {
public int countPalindromicSubsequences(String s) {
final int MOD = 1000000007;
int n = s.length();
int[][][] dp = new int[4][n][n];
for (int i = 0; i < n; i++) {
dp[s.charAt(i) - 'a'][i][i] = 1;
}
for (int len = 2; len <= n; len++) {
for (int i = 0; i + len <= n; i++) {
int j = i + len - 1;
for (char c = 'a'; c <= 'd'; c++) {
int k = c - 'a';
if (s.charAt(i) == c && s.charAt(j) == c) {
dp[k][i][j] = (2 + (dp[0][i + 1][j - 1] + dp[1][i + 1][j - 1]) % MOD + (dp[2][i + 1][j - 1] + dp[3][i + 1][j - 1]) % MOD) % MOD;
} else if (s.charAt(i) == c) {
dp[k][i][j] = dp[k][i][j - 1];
} else if (s.charAt(j) == c) {
dp[k][i][j] = dp[k][i + 1][j];
} else {
dp[k][i][j] = dp[k][i + 1][j - 1];
}
}
}
}
int res = 0;
for (int i = 0; i < 4; i++) {
res = (res + dp[i][0][n - 1]) % MOD;
}
return res;
}
}
python3 解法, 执行用时: 3096 ms, 内存消耗: 49.4 MB, 提交时间: 2023-02-26 11:44:27
'''
动态规划+三维数组
dp[x][i][j] 表示在字符串s[i:j]中以x为开头和结尾的不同回文序列总数
'''
class Solution:
def countPalindromicSubsequences(self, s: str) -> int:
MOD = 10 ** 9 + 7
n = len(s)
dp = [[[0] * n for _ in range(n)] for _ in range(4)]
for i, c in enumerate(s):
dp[ord(c) - ord('a')][i][i] = 1
for sz in range(2, n + 1):
for j in range(sz - 1, n):
i = j - sz + 1
for k, c in enumerate("abcd"):
if s[i] == c and s[j] == c:
dp[k][i][j] = (2 + sum(d[i + 1][j - 1] for d in dp)) % MOD
elif s[i] == c:
dp[k][i][j] = dp[k][i][j - 1]
elif s[j] == c:
dp[k][i][j] = dp[k][i + 1][j]
else:
dp[k][i][j] = dp[k][i + 1][j - 1]
return sum(d[0][n - 1] for d in dp) % MOD
java 解法, 执行用时: 64 ms, 内存消耗: 49.2 MB, 提交时间: 2023-02-26 11:41:03
class Solution {
public int countPalindromicSubsequences(String s) {
int mod = 1000000007;
int n = s.length();
int[][] dp = new int[n][n];
//一个单字符是一个回文子序列
for (int i = 0; i < n; i++) {
dp[i][i] = 1;
}
//从长度为2的子串开始计算
for (int len = 2; len <= n; len++) {
//挨个计算长度为len的子串的回文子序列个数
for (int i = 0; i + len <= n; i++) {
int j = i + len - 1;
//情况(1) 相等
if (s.charAt(i) == s.charAt(j)) {
int left = i + 1;
int right = j - 1;
//找到第一个和s[i]相同的字符
while (left <= right && s.charAt(left) != s.charAt(i)) {
left++;
}
//找到第一个和s[j]相同的字符
while (left <= right && s.charAt(right) != s.charAt(j)) {
right--;
}
if (left > right) {
//情况① 没有重复字符
dp[i][j] = 2 * dp[i + 1][j - 1] + 2;
} else if (left == right) {
//情况② 出现一个重复字符
dp[i][j] = 2 * dp[i + 1][j - 1] + 1;
} else {
//情况③ 有两个及两个以上
dp[i][j] = 2 * dp[i + 1][j - 1] - dp[left + 1][right - 1];
}
} else {
//情况(2) 不相等
dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1];
}
//处理超范围结果
dp[i][j] = (dp[i][j] >= 0) ? dp[i][j] % mod : dp[i][j] + mod;
}
}
return dp[0][n - 1];
}
}
python3 解法, 执行用时: 1228 ms, 内存消耗: 37.5 MB, 提交时间: 2023-02-26 11:40:40
'''
dp[i][j] 表示从i到j回文字符串的个数
'''
class Solution:
def countPalindromicSubsequences(self, s: str) -> int:
mod = 1000000007
n = len(s)
dp = [[0] * n for _ in range(n)]
for i in range(n): dp[i][i] = 1
for cur_len in range(2, n+1): # 从长度为2的子串开始计算
# 挨个计算长度为len的子串的回文子序列个数
for i in range(0, n-cur_len+1):
j = i+ cur_len -1
# 情况(1) 相等
if s[i] == s[j]:
l, r = i+1, j-1
while l <= r and s[l] != s[i]: l += 1
while l <= r and s[r] != s[j]: r -= 1
if l > r: # 情况① 没有重复字符
dp[i][j] = 2 * dp[i+1][j-1] + 2
elif l == r: # 情况② 出现一个重复字符
dp[i][j] = 2 * dp[i+1][j-1] + 1
else: # 情况③ 有两个及两个以上
dp[i][j] = 2 * dp[i+1][j-1] - dp[l+1][r-1]
else: # 情况(2) 不相等
dp[i][j] = dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1]
dp[i][j] = dp[i][j] % mod # Python直接取模也没有问题
return dp[0][n-1]