[2022-06-10]730. 统计不同回文子序列👋字符串👋动态规划

[webVueBlog]

题目链接: https://leetcode-cn.com/problems/count-different-palindromic-subsequences

难度: Hard
标签: 字符串 动态规划

[dreamjean]

730. 统计不同回文子序列

Description

Difficulty: 困难

Related Topics: 字符串, 动态规划

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

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

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

如果有某个 i , 满足 a_i != b_i，则两个序列 a₁, a₂, ... 和 b₁, b₂, ... 不同。

注意：

• 结果可能很大，你需要对 10⁹ + 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' 

Solution

思路： 二维dp

• 使用一个二维数组dp分别记录回文串的左右两个端点的回文数量
• 初始化 dp， 每个单独的字母都是一个回文子序列，因此 dp(i, i) = 1
• i 和 j分别代表回文子串的左右两个端点，计算回文个数时是以中心扩散到两端来计算，因此 i 和 j 的上一步分别为 i + 1 ， j - 1,
• 当 s[i] != s[j] 时，dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1] ，i + 1 和 j - 1,即左右两边的各自上一步的值相加去减去重复计算的部分
• 当 s[i] = s[j] 时, dp(l, r) 代表回文子序列 s[l ... r] 的数量, 此时 dp(l, r) 需要分类讨论：
  _ 先初始化 dp(l, r) : 2 * dp(i + 1， j - 1)，如 aa
  • l = r: +1 , 如果出现一次，那么需要添加一个字符的最大可能
  • l > r: +2, 没有出现回文子序列，此时需要添加最大的可能的2个字符的回文数，如 a a 可以组成 a 和 aa
  • l < r: -dp(l + 1, r - 1) 如果有出现2次，就需要删除重复添加的数量
• 最后添加mod防止溢出

Language: JavaScript

/**
 * @param {string} s
 * @return {number}
 */
var countPalindromicSubsequences = function(s) {
    const [mod, n] = [1e9 + 7, s.length];
    const dp = Array.from({ length: n }, () => new Array(n).fill(0));

    for (let i = 0; i < n; i++) dp[i][i] = 1;

    for (let k = 1; k < n; k++) {
        for (let i = 0; i < n - k; i++) {
            let j = i + k;
            if (s[i] !== s[j]) dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1];
            
            else {
                dp[i][j] = 2 * dp[i + 1][j - 1];
                let [l, r] = [i + 1, j - 1];

                while (l <= r && s[l] !== s[i]) l++;
                while (l <= r && s[r] !== s[i]) r--;

                if (l === r) dp[i][j]++;
                l > r ? dp[i][j] += 2 : dp[i][j] -= dp[l + 1][r - 1];      
            } 

            dp[i][j] = (dp[i][j] + mod) % mod;
        }
    }

    return dp[0][n - 1];
};