[LeetCode] 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个字母。然后说最终结果要对一个很大的数字取余,这就暗示了结果会是一个很大的值,那么对于这种问题一般都是用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]的值对超大数取余,将该值返回即可,参见代码如下:

解法一:

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 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中间部分的子序列个数的原因是其被计算了两遍,要将多余的减掉。

参见代码如下:

解法二:

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 SubstringPalindromic 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 计数不同的回文子序列的个数

,如需转载请自行联系原博主。

时间: 2024-10-23 05:13:17

[LeetCode] Count Different Palindromic Subsequences 计数不同的回文子序列的个数的相关文章

Longest Palindromic Substring:最长回文子串

题目链接 Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring. 求字符串的最长回文子串 算法1:暴力解法,枚举所有子串,对每个子串判断是否为回文,复杂度为O(n^3) 算法2:删除暴力解法中有很多重复的判

[LeetCode] Palindrome Number &amp;amp; Valid Palindrome - 回文系列问题

题目概述: Determine whether an integer is a palindrome. Do this without extra space. 题目分析: 判断数字是否是回文 例如121.656.3443 方法有很多,正着看和到着看两数相同:当然负数显然不是回文 我的方法: 第一种方法: 由于没有没有看到前面的without extra space.采用的方法是把数字转换为字符串,依次比较最前和最后两个字符是否相同,直到遍历完毕. /** * 判断一个数字是否是回文数字 Pal

leetcode 5 Longest Palindromic Substring--最长回文字符串

问题描述 Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring. 所谓回文字符串,就是一个字符串,从左到右读和从右到左读是完全一样的.比如"a" , "aaabbaaa" 之前

[LeetCode] Count Binary Substrings 统计二进制子字符串

Give a string s, count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively. Substrings that occur multiple times are counted the numbe

[LeetCode] Palindromic Substrings 回文子字符串

Given a string, your task is to count how many palindromic substrings in this string. The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters. Example 1: Input: "abc" Ou

[LeetCode]5.Longest Palindromic Substring

题目 Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring. 思路一 即不使用技巧,穷举所有可能.时间复杂度为O(n^3)(时间上最长,不推荐使用),空间复杂度为O(1).本思路是从最大长度的字串开始,而不

[LeetCode] Split Array into Consecutive Subsequences 将数组分割成连续子序列

You are given an integer array sorted in ascending order (may contain duplicates), you need to split them into several subsequences, where each subsequences consist of at least 3 consecutive integers. Return whether you can make such a split. Example

LeetCode 5 Longest Palindromic Substring(最大回文子字符串)

翻译 给定一个字符串S,找出它的最大回文子字符串. 你可以假定S的最大长度为1000, 并且这里存在唯一一个最大回文子字符串. 原文 Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring. 暴力搜索,O(n

LeetCode 9 Palindrome Number (回文数)

翻译 确定一个整数是否是回文数.不能使用额外的空间. 一些提示: 负数能不能是回文数呢?(比如,-1) 如果你想将整数转换成字符串,但要注意限制使用额外的空间. 你也可以考虑翻转一个整数. 然而,如果你已经解决了问题"翻转整数(译者注:LeetCode 第七题), 那么你应该知道翻转的整数可能会造成溢出. 你将如何处理这种情况? 这是一个解决该问题更通用的方法. 原文 Determine whether an integer is a palindrome. Do this without ex