Python描述 LeetCode 730. 統計不同回文子序列

  大家好，我是亓官劼（qí guān jié ），在【亓官劼】公衆号、、GitHub、B站等平台分享一些技術博文，主要包括前端開發、python後端開發、小程式開發、資料結構與算法、docker、Linux常用運維、NLP等相關技術博文，時光荏苒，未來可期，加油~

  如果喜歡部落客的文章可以關注部落客的個人公衆号【亓官劼】(qí guān jié)，裡面的文章更全更新更快。如果有需要找部落客的話可以在公衆号背景留言，我會盡快回複消息.

本文原創為【亓官劼】（qí guān jié ），請大家支援原創，部分平台一直在惡意盜取部落客的文章！！！ 全部文章請關注微信公衆号【亓官劼】。

題目

給定一個字元串 s，傳回 ​

​s​

​ 中不同的非空「回文子序列」個數 。

通過從 s 中删除 0 個或多個字元來獲得子序列。

如果一個字元序列與它反轉後的字元序列一緻，那麼它是「回文字元序列」。

如果有某個 ​

​i​

​​ , 滿足 ​

​ai != bi​

​​ ，則兩個序列 ​

​a1, a2, ...​

​​ 和 ​

​b1, b2, ...​

​ 不同。

注意：

• 結果可能很大，你需要對​

  ​109 + 7​

  ​ 取模 。

示例 1：

輸入：s = 'bccb'
輸出：6
解釋：6 個不同的非空回文子字元序列分别為：'b', 'c', 'bb', 'cc', 'bcb', 'bccb'。
注意：'bcb' 雖然出現兩次但僅計數一次。      

示例 2：

輸入：s = 'abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba'
輸出：104860361
解釋：共有 3104860382 個不同的非空回文子序列，104860361 對 109 + 7 取模後的值。      

提示：

• ​

  ​1 <= s.length <= 1000​

  ​
• ​

  ​s[i]​

  ​​ 僅包含​

  ​'a'​

  ​​,​

  ​'b'​

  ​​,​

  ​'c'​

  ​​ 或​

  ​'d'​

  ​

解題思路

1. char == s[i] == s[j]：兩端的字元都是char，則這兩個字元本身就可以組成(char)和(char char)兩個回文子串，其次在s[i+1:j]中所有的回文子串加上兩端的char都是回文子串，即dp[char][i][j] = sum(item[i+1][j-1] for item in dp)
2. s[i] != s[j] and char == s[i]:  右端字元不是char，直接删除該字元，dp[char][i][j] = dp[char][i][j-1]
3. s[i] != s[j] and char == s[j]: 左端字元不是char，直接删除該字元，dp[char][i][j] = dp[char][i+1][j]
4. s[i] != s[j] and char != s[i] and char != s[j]: 兩端都不是該字元，兩端都删除,dp[char][i][j] = dp[char][i+1][j-1]      

Python描述

class Solution:
    def countPalindromicSubsequences(self, s: str) -> int:
        MOD = 10**9 + 7
        n = len(s)
        # dp[char][i][j]: s[i:j+1]可以删成兩端為char的回文子串數量
        dp = [[[0 for i in range(n)] for j in range(n)] for _ in range(4)]
        # 初始化：長度為1時，可以構成一個回文子串
        for idx,ch in enumerate("abcd"):
            for i in range(n):
                if ch == s[i]:
                    dp[idx][i][i] = 1
        
        # 子串長度：2 - n
        for length in range(2,n+1):
            for j in range(length-1,n):
                i = j - length + 1
                for idx,ch in enumerate("abcd"):
                    if ch == s[i] == s[j]:
                        dp[idx][i][j] = 2 + sum(item[i+1][j-1] for item in dp)
                    elif ch == s[i]:
                        dp[idx][i][j] = dp[idx][i][j-1]
                    elif ch == s[j]:
                        dp[idx][i][j] = dp[idx][i+1][j]
                    else:
                        dp[idx][i][j] = dp[idx][i+1][j-1]
        
        res = sum([item[0][n-1] for item in dp]) % MOD
        return