730. Count Different Palindromic Subsequences

 

Given a string S, find the number of different non-empty palindromic subsequences in S, and return that number modulo 10^9 + 7.

A subsequence of a string S is obtained by deleting 0 or more characters from S.

A sequence is palindromic if it is equal to the sequence reversed.

Two sequences A_1, A_2, ... and B_1, B_2, ... are different if there is some i for which A_i != B_i.

Example 1:

Input: 
S = 'bccb'
Output: 6
Explanation: 
The 6 different non-empty palindromic subsequences are 'b', 'c', 'bb', 'cc', 'bcb', 'bccb'.
Note that 'bcb' is counted only once, even though it occurs twice.

 

Example 2:

Input: 
S = 'abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba'
Output: 104860361
Explanation: 
There are 3104860382 different non-empty palindromic subsequences, which is 104860361 modulo 10^9 + 7.

 

Note:

  • The length of S will be in the range [1, 1000].
  • Each character S[i] will be in the set {'a', 'b', 'c', 'd'}.

 

这道题给了给了我们一个字符串,让求出所有的非空回文子序列的个数,虽然这题限制了字符只有四种,但还是按一般的情况来解吧,可以有 26 个字母。说最终结果要对一个很大的数字取余,这就暗示了结果会是一个很大的值,对于这种问题一般都是用动态规划 Dynamic Programming 或者是带记忆数组 memo 的递归来解,二者的本质其实是一样的。先来看带记忆数组 memo 的递归解法,这种解法的思路是一层一层剥洋葱,比如 “bccb”,按照字母来剥,先剥字母b,确定最外层 “b _ _ b”,这会产生两个回文子序列 “b” 和 “bb”,然后递归进中间的部分,把中间的回文子序列个数算出来加到结果 res 中,中间的 “cc” 调用递归会返回2,两边都加上b,会得到 “bcb”, “bccb”,此时结果 res 为4。然后开始剥字母c,找到最外层 “cc”,此时会产生两个回文子序列 “c” 和 “cc”,由于中间没有字符串了,所以递归返回0,最终结果 res 为6,按照这种方法就可以算出所有的回文子序列了。

建立一个二维数组 chars,外层长度为 26,里面放一个空数组。这是为了统计每个字母在原字符串中出现的位置,然后定义一个二维记忆数组 memo,其中 memo[i][j] 表示第i个字符到第j个字符之间的子字符串中的回文子序列的个数,初始化均为0。然后遍历字符串S,将每个字符的位置加入其对应的数组中,比如对于 “bccb”,那么有:

b -> {0, 3}

c -> {1, 2}

然后在 [0, n] 的范围内调用递归函数,在递归函数中,首先判断如果 start 大于等于 end,返回0。如果当前位置在 memo 的值大于0,说明当前情况已经计算过了,直接返回 memo 数组中的值。否则进行所有字母的遍历,如果某个字母对应的数组中没有值,说明该字母不曾在字符串中出现,跳过。然后在字母数组中查找第一个不小于 start 的位置,查找第一个小于 end 的位置,当前循环中,start 为0,end 为4,当前处理字母b,new_start 指向0,new_end 指向3,如果当前 new_start 指向了 end(),或者其指向的位置大于 end,说明当前范围内没有字母b,直接跳过,否则结果 res 自增1,因为此时 new_start 存在,至少有个单个的字母b,也可以当作回文子序列,然后看 new_start 和 new_end 如果不相同,说明两者各指向了不同的b,此时 res 应自增1,因为又增加了一个新的回文子序列 “bb”,下面就是对中间部分调用递归函数了,把返回值加到结果 res 中。此时字母b就处理完了,现在处理字母c,此时的 start 还是0,end 还是4,new_start 指向1,new_end 指向2,跟上面的分析相同,new_start 在范围内,结果自增1,因为加上了 “c”,然后 new_start 和 new_end 不同,结果 res 再自增1,因为加上了 “cc”,其中间没有字符了,调用递归的结果是0,for 循环结束,将 memo[start][end] 的值对超大数取余,并将该值返回即可,参见代码如下:

 

解法一:

class Solution {
public:
    int countPalindromicSubsequences(string S) {
        int n = S.size();
        vector<vector<int>> chars(26, vector<int>());
        vector<vector<int>> memo(n + 1, vector<int>(n + 1, 0));
        for (int i = 0; i < n; ++i) {
            chars[S[i] - 'a'].push_back(i);
        }
        return helper(S, chars, 0, n, memo);
    }
    int helper(string S, vector<vector<int>>& chars, int start, int end, vector<vector<int>>& memo) {
        if (start >= end) return 0;
        if (memo[start][end] > 0) return memo[start][end];
        long res = 0;
        for (int i = 0; i < 26; ++i) {
            if (chars[i].empty()) continue;
            auto new_start = lower_bound(chars[i].begin(), chars[i].end(), start);
            auto new_end = lower_bound(chars[i].begin(), chars[i].end(), end) - 1;
            if (new_start == chars[i].end() || *new_start >= end) continue;
            ++res;
            if (new_start != new_end) ++res;
            res += helper(S, chars, *new_start + 1, *new_end, memo);
        }
        memo[start][end] = res % int(1e9 + 7);
        return memo[start][end];
    }
};

 

我们再来看一种迭代的写法,使用一个二维的 dp 数组,其中 dp[i][j] 表示子字符串 [i, j] 中的不同回文子序列的个数,初始化 dp[i][i] 为1,因为任意一个单个字符就是一个回文子序列,其余均为0。这里的更新顺序不是正向,也不是逆向,而是斜着更新,对于 “bccb” 的例子,其最终 dp 数组如下,可以看到其更新顺序分别是红-绿-蓝-橙。

 

  b c c b  
b 1 2 3 6
c 0 1 2 3
c 0 0 1 2
b 0 0 0 1

 

这样更新的好处是,更新当前位置时,其左,下,和左下位置的 dp 值均已存在,而当前位置的 dp 值需要用到这三个位置的 dp 值。观察上面的 dp 数组,可以发现当 S[i] 不等于 S[j] 的时候,dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1],即当前的 dp 值等于左边值加下边值减去左下值,因为算左边值的时候包括了左下的所有情况,而算下边值的时候也包括了左下值的所有情况,那么左下值就多算了一遍,所以要减去。而当 S[i] 等于 S[j] 的时候,情况就比较复杂了,需要分情况讨论,因为不知道中间还有几个和 S[i] 相等的值。举个简单的例子,比如 “aba” 和 “aaa”,当 i = 0, j = 2 的时候,两个字符串均有 S[i] == S[j],此时二者都新增两个子序列 “a” 和 “aa”,但是 “aba” 中间的 “b” 就可以加到结果 res 中,而 “aaa” 中的 “a” 就不能加了,因为和外层的单独 “a” 重复了。我们的目标就要找到中间重复的 “a”。所以让 left = i + 1, right = j - 1,然后对 left 进行 while 循环,如果 left <= right, 且 S[left] != S[i] 的时候,left 向右移动一个;同理,对 right 进行 while 循环,如果 left <= right, 且 S[right] != S[i] 的时候,left 向左移动一个。这样最终 left 和 right 值就有三种情况:

1. 当 left > righ 时,说明中间没有和 S[i] 相同的字母了,就是 “aba” 这种情况,那么就有 dp[i][j] = dp[i + 1][j - 1] * 2 + 2,其中 dp[i + 1][j - 1] 是中间部分的回文子序列个数,为啥要乘2呢,因为中间的所有子序列可以单独存在,也可以再外面包裹上字母a,所以是成对出现的,要乘2。加2的原因是外层的 “a” 和 “aa” 也要统计上。

2. 当 left = right 时,说明中间只有一个和 S[i] 相同的字母,就是 “aaa” 这种情况,那么有 dp[i][j] = dp[i + 1][j - 1] * 2 + 1,其中乘2的部分跟上面的原因相同,加1的原因是单个字母 “a” 的情况已经在中间部分算过了,外层就只能再加上个 “aa” 了。

3. 当 left < right 时,说明中间至少有两个和 S[i] 相同的字母,就是 “aabaa” 这种情况,那么有 dp[i][j] = dp[i + 1][j - 1] * 2 - dp[left + 1][right - 1],其中乘2的部分跟上面的原因相同,要减去 left 和 right 中间部分的子序列个数的原因是其被计算了两遍,要将多余的减掉。比如说对于  “aabaa”,当检测到 S[0] == S[4] 时,是要根据中间的 “aba” 的回文序列个数来计算,共有四种,分别是 “a”, “b”, “aa”, “aba”,将其分别在左右两边加上a的话,可以得到 “aaa”, “aba”, “aaaa”, “aabaa”,我们发现 “aba” 出现了两次了,这就是要将 dp[2][2] (left = 1, right = 3) 减去的原因。

参见代码如下:

 

解法二:

class Solution {
public:
    int countPalindromicSubsequences(string S) {
        int n = S.size(), M = 1e9 + 7;
        vector<vector<int>> dp(n, vector<int>(n, 0));
        for (int i = 0; i < n; ++i) dp[i][i] = 1;
        for (int len = 1; len < n; ++len) {
            for (int i = 0; i < n - len; ++i) {
                int j = i + len;
                if (S[i] == S[j]) {
                    int left = i + 1, right = j - 1;
                    while (left <= right && S[left] != S[i]) ++left;
                    while (left <= right && S[right] != S[i]) --right;
                    if (left > right) {
                        dp[i][j] = dp[i + 1][j - 1] * 2 + 2;
                    } else if (left == right) {
                        dp[i][j] = dp[i + 1][j - 1] * 2 + 1;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1] * 2 - dp[left + 1][right - 1];
                    }
                } else {
                    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] + M : dp[i][j] % M;
            }
        }
        return dp[0][n - 1];
    }
};

 

讨论:这道题确实是一道很难的题,和它类似的题目还有几道,虽然那些题有的还有非 DP 解法,但是 DP 解法始终是核心的,也是我们最应该掌握的方法。首先要分清子串和子序列的题,个人感觉子序列要更难一些。在之前那道 Longest Palindromic Subsequence 中要求最长的回文子序列,需要逆向遍历 dp 数组,当 s[i] 和 s[j] 相同时,长度为中间部分的 dp 值加2,否则就是左边值和下边值中的较大值,因为是子序列,不匹配就可以忽略当前字符。而对于回文子串的问题,比如 Longest Palindromic Substring 和 Palindromic Substrings,一个是求最长的回文子串,一个是求所有的回文子串个数,他们的 dp 定义是看子串 [i, j] 是否是回文串,求最长回文子串就是维护一个最大值,不停用当前回文子串的长度更新这个最大值,同时更新最大值的左右边界。而求所有回文子串的个数就是如果当前 dp[i][j] 判断是回文串,计数器就自增1。而判断当前 dp[i][j] 是否是回文串的核心就是 s[i]==s[j],且 i,j 中间没有字符了,或者中间的 dp 值为 true。

 

Github 同步地址:

https://github.com/grandyang/leetcode/issues/730

 

类似题目:

Longest Palindromic Subsequence

Longest Palindromic Substring

Palindromic Substrings

 

参考资料:

https://leetcode.com/problems/count-different-palindromic-subsequences/

https://leetcode.com/problems/count-different-palindromic-subsequences/discuss/109509/Accepted-Java-Solution-using-memoization

https://leetcode.com/problems/count-different-palindromic-subsequences/discuss/109507/Java-96ms-DP-Solution-with-Detailed-Explanation

 

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation