LeetCode730. 统计不同回文子序列

题目描述

本题目来自LeetCode上的『730. 统计不同回文子序列』

给定一个字符串 s，返回 s 中不同的非空「回文子序列」个数。

通过从 s 中删除 0 个或多个字符来获得子序列。

如果一个字符序列与它反转后的字符序列一致，那么它是「回文字符序列」。

如果有某个 i , 满足 ai != bi ，则两个序列 a1, a2, ... 和 b1, b2, ... 不同。

注意：

结果可能很大，你需要对 10^9 + 7 取模。

示例1：

输入：s = ‘bccb’
输出：6
解释：6 个不同的非空回文子字符序列分别为：’b’, ‘c’, ‘bb’, ‘cc’, ‘bcb’, ‘bccb’。
注意：’bcb’ 虽然出现两次但仅计数一次。

示例2：

输入：s = ‘abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba’
输出：104860361
解释：共有 3104860382 个不同的非空回文子序列，104860361 对 10e9 + 7 取模后的值。

提示

1 <= s.length <= 1000
s[i] 仅包含 'a', 'b', 'c' 或 'd'

题解

设 $dp[c][i][j]$ 为首位字母为 $c$，且在字符串 $s[i…j]$ 中的回文序列的个数，分类讨论：

$s[i]=c\wedge s[j]=c$，此时任意字符串 $s[i+1…j-1]$ 的回文序列在两侧加上字符 $c$，都还是回文序列，除了以 $c$ 开头的字符串 $s[i+1…j-1]$ 之外，其他的字符串还多了 $cc$，$c$ 这两个回文序列，因此有:
$$
dp[c][i][j]=2+\sum\limits_{c_k\in C}dp[c_k][i+1][j-1]
$$
$s[i]=c\wedge s[j]\ne c$，此时 $s[j]$ 不会对以 $c$ 为首尾的字符串包含的回文序列产生贡献，因此有:
$$
dp[c][i][j]=dp[c][i][j-1]
$$
$s[i]\ne c\wedge s[j]= c$，此时 $s[i]$ 不会对以 $c$ 为首尾的字符串包含的回文序列产生贡献，因此有:
$$
dp[c][i][j]=dp[c][i+1][j]
$$
$s[i]\ne c\wedge s[j]\ne c$，此时 $s[i]$ 和 $s[j]$ 都不会对以 $c$ 为首尾的字符串包含的回文序列产生贡献，因此有:
$$
dp[c][i][j]=dp[c][i+1][j-1]
$$

考虑初始条件，当只有一个字符的时候，回文序列的个数为 $1$，即 $dp[c][i][i]=1$
注：使用普通的递归会 TLE，Python在使用 @cache 开启记忆化递归后，可以通过，虽然还是很慢（3220 ms）

代码

class Solution {
private:
    static constexpr int MOD = 1e9 + 7;
public:
    int countPalindromicSubsequences(string s) {
        int n = s.size();
        int dp[4][1010][1010] = {0};
        for (int i = 0; i < n; ++i) {
            dp[s[i] - 'a'][i][i] = 1;
        }

        for (int len = 2; len <= n; ++len) {
            for (int i = 0, j = len - 1; j < n; ++i, ++j) {
                for (int k = 0; k < 4; ++k) {
                    char c = 'a' + k;
                    if (s[i] == c && s[j] == c) {
                        for (int ck = 0; ck < 4; ++ck) {
                            dp[k][i][j] += dp[ck][i + 1][j - 1];
                            dp[k][i][j] %= MOD;
                        }
                        dp[k][i][j] = (dp[k][i][j] + 2) % MOD;
                    } else if (s[i] == c && s[j] != c) {
                        dp[k][i][j] = dp[k][i][j - 1];
                    } else if (s[i] != c && s[j] == c) {
                        dp[k][i][j] = dp[k][i + 1][j];
                    } else {
                        dp[k][i][j] = dp[k][i + 1][j - 1];
                    }
                }
            }
        }

        int ans = 0;
        for (int i = 0; i < 4; ++i) {
            ans += dp[i][0][n - 1];
            ans %= MOD;
        }

        return ans;
    }
};

代码-记忆优化递归

class Solution:
    def countPalindromicSubsequences(self, s: str) -> int:
        MOD = int(1e9 + 7)

        @cache
        def dfs(c : str, i: int, j: int) -> int:
            if i >= j:
                return int(i == j and s[i] == c)
            if s[i] == c and s[j] == c:
                return (sum(dfs(ck, i + 1, j - 1) for ck in 'abcd') + 2) % MOD
            if s[i] == c:
                return dfs(c, i, j - 1)
            if s[j] == c:
                return dfs(c, i + 1, j)
            return dfs(c, i + 1, j - 1)

        return sum(dfs(c, 0, len(s) - 1) for c in 'abcd') % MOD