0730._Count_Different_Palindromic_Subsequences.md

730. Count Different Palindromic Subsequences

难度: Hard

刷题内容

原题连接

• https://leetcode.com/problems/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'}.

解题方案

思路 1 - 时间复杂度: O(N^2)- 空间复杂度: O(N)******

递归，对于一个字符串S，最外层只能有'abcd'其中一对，分四种情况讨论，'aa','bb','cc','dd', 然后如果组不成一对的时候，那就只有1个毫无疑问，比如'a'。

下面代码中的+2指的是比如'a******a'，我们这里有两种方式：

• 可以只取一个'a'和里面全是'a'的结果结合作为结果
• 另外一种就是'a' + '里面的结果' + 'a'

如果i == j说明整个字符串种只有一个'a'，那自然+1，因为只有包含'a'的结果只有'a'一种

思路参考flamesofmoon

beats 30.17%

class Solution:
    def countPalindromicSubsequences(self, S):
        """
        :type S: str
        :rtype: int
        """
        def helper(start, end): # res for S[start:end]
            if (start, end) in self.cache:
                return self.cache[(start, end)]
            res = 0
            for char in 'abcd':
                l, r = S[start:end].find(char), S[start:end][::-1].find(char)
                if l != -1 and r != -1:
                    i = start + l
                    j = end - 1 - r
                    res += helper(i+1, j) + 2 if i != j else 1
            self.cache[(start, end)] = res % (10**9 + 7)
            return self.cache[(start, end)]
        
        self.cache = {}
        return helper(0, len(S))