730.md

Count Different Palindromic Subsequences

Description

link

---

Solution

• 因为所有字符都在abcd当中，所以可以统计头尾是同样字符的情况下：
  • 有a，aa两种一定可以组成回文的情况
  • 还有a*a的情况，只需要dfs ** 得到结果即可
  • 为了防止重复计算，cache保存对应的答案

---

Code

Complexity T : O(n^2) M : O(n^2)

class Solution:
    def countPalindromicSubsequences(self, S: str) -> int:
        def cache(start, end):            # This function serves to save the result
            if end <= start + 2:          # simple cases can be computed directly
                return end - start
            
            if (start, end) not in check: # if not saved, compute and save before returning
                check[(start, end)] = DFS(start, end)
                
            return check[(start, end)]
        
        def DFS(start, end):     #returns the number of distinct palindromes in S[start:end]
            count = 0
            segment = S[start:end]
            
            for x in 'abcd':
                try:
                    i = segment.index(x) + start  # the starting index in S
                    j = segment.rindex(x) + start # the ending index in S
                except:
                    continue
                    
                count += cache(i+1, j) + 2 if i != j else 1

            return count % 1000000007
                
        check = {}
        return cache(0, len(S))