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个字母。然后说最终结果要对一个很大的数字取余,这就暗示了结果会是一个很大的值,那么对于这种问题一般都是用DP或者是带记忆数组memo的递归来解,二者的本质其实是一样的。我们先来看带记忆数组memo的递归解法,这种解法的思路是一层一层剥洋葱,比如"bccb",按照字母来剥,先剥字母b,确定最外层"b _ _ b",这会产生两个回文子序列"b"和"bb",然后递归进中间的部分,把中间的回文子序列个数算出来加到结果res中,然后开始剥字母c,找到最外层"cc",此时会产生两个回文子序列"c"和"cc",然后由于中间没有字符串了,所以递归返回0,按照这种方法就可以算出所有的回文子序列了。
我们建立一个二维数组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]的值对超大数取余,将该值返回即可,参见代码如下:
解法一:
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 bb 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中间部分的子序列个数的原因是其被计算了两遍,要将多余的减掉。
参见代码如下:
解法二:
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。
参考资料:
https://discuss.leetcode.com/topic/111230/accepted-java-solution-using-memoization
https://discuss.leetcode.com/topic/111483/java-96ms-dp-solution-with-detailed-explanation
本文转自博客园Grandyang的博客,原文链接:[LeetCode] Count Different Palindromic Subsequences 计数不同的回文子序列的个数
,如需转载请自行联系原博主。