给定一个字符串 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' 虽然出现两次但仅计数一次。
var countPalindromicSubsequences = function(s) {
const n = s.length, MOD = 10 ** 9 + 7
const dp = Array.from({length: 4}, _ => Array.from({length: n}, _ => new Uint32Array(n)))
for (let i = 0; i < n; i++) dp[s.charCodeAt(i) - 97][i][i] = 1
for (let len = 2; len <= n; len++) {
for (let i = 0; i + len <= n; i++) {
const j = i + len - 1, a = s.charCodeAt(i) - 97, b = s.charCodeAt(j) - 97
for (let k = 0; k < 4; k++) {
if (a === k && b === k) {
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 (a === k) {
dp[k][i][j] = dp[k][i][j - 1]
} else if (b === k) {
dp[k][i][j] = dp[k][i + 1][j]
} else {
dp[k][i][j] = dp[k][i + 1][j - 1]
}
}
}
}
let sum = 0
for (let k = 0; k < 4; k++) sum = (sum + dp[k][0][n - 1]) % MOD
return sum
};
function countPalindromicSubsequences(s: string): number {
const n = s.length
const dp = Array.from({length: n}, _ => new Int32Array(n))
const MOD = 1e9 + 7
for (let i = 0; i < n; i++) dp[i][i] = 1
for (let len = 2; len <= n; len++) {
for (let i = 0; i + len <= n; i++) {
const j = i + len - 1
if (s[i] !== s[j]) dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1]
else {
dp[i][j] = 2 + dp[i + 1][j - 1] * 2
let l = i + 1, r = j - 1
while (l <= r && s[l] !== s[i]) l++
while (l <= r && s[r] !== s[i]) r--
if (l === r) dp[i][j]-- // 1 个相同
if (l < r) dp[i][j] -= dp[l + 1][r - 1] + 2 // >= 2 个相同
}
dp[i][j] = dp[i][j] < 0 ? dp[i][j] + MOD : dp[i][j] % MOD
}
}
return dp[0][n - 1]
};