化簡無所不在 用LCS的DP模型解 最長回文子序列 Longest Palindromic Subseq_LC#516

Anthony DELANOIX on Unsplash

題目敘述 Longest Palindromic Subsequence

給定一個字串s，請找出字串s的最長回文子序列的長度。

註: 子序列 不要求一定要連續。

測試範例

Example 1:

Input: s = "bbbab"
Output: 4
Explanation: One possible longest palindromic subsequence is "bbbb".

最長回文子序列是'bbbb'的長度為4​

Example 2:

Input: s = "cbbd"
Output: 2
Explanation: One possible longest palindromic subsequence is "bb".

最長回文子序列是'bb'的長度為4​

約束條件

Constraints:

• 1 <= s.length <= 1000

輸入字串s的長度介於1~1000之間。

• s consists only of lowercase English letters.

輸入字串s只會有小寫英文字母。

觀察 LCS+ s 與 逆序的s去尋找共同子序列

最長回文子序列 可以怎麼找?

回文，代表內容一定是左右對稱，而且相等。

最長回文子序列，代表一定是在s內部尋找回文的結構。

前面已經學過Longest Common Subsequebce 最長共同子序列

那我們只要把s 和 s逆序 = s[::-1] 傳入LCS最長共同子序列的演算法，

就可以找到Longest Palindromic Subsequence最長回文子序列。

以s='bbbab'為例子:

LCS('bbbab', 'babbb') = 'bbbb' = LPS('bbbab)

為什麼?

因為字串s 和 s逆序找出來的共同子序列的順序，剛好一左一右，前後顛倒，內容相等。

進而保障s 和 s逆序 找到的共同子序列一定是回文子序列，
推理出 s 和 s逆序 最長的共同子序列也一定是最長回文子序列

字串s 和 s逆序 最長的共同子序列

= LCS(s, s[::-1]) = LPS(s) = 字串s的最長回文子序列

演算法 化簡到LCS的DP模型

承接觀察點的思考，

字串s 和 s逆序找出來的共同子序列的順序，剛好一左一右，前後顛倒，內容相等。

進而保障s 和 s逆序 找到的共同子序列一定是回文子序列，

推理出 s 和 s逆序 最長的共同子序列也一定是最長回文子序列，

那我們只要把s 和 s逆序 = s[::-1] 傳入LCS最長共同子序列的演算法，

就可以找到Longest Palindromic Subsequence最長回文子序列。

程式碼 化簡到LCS的DP模型

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        # -------------------------------------------------
        # DP table
        dp = {}

        def LCS(i, j):

            if (i, j) in dp:
                # Look-up DP table
                return dp[i, j]

            if i == -1 or j == -1:
                # Any string compare to empty string has no common sequence
                dp[i, j] = 0
                return 0

            elif text1[i] == text2[j]:
                # Current character is the same
                dp[i, j] = LCS(i-1, j-1) + 1
                return dp[i, j]

            else:
                # Current characters are different
                dp[i, j] = max( LCS(i-1, j), LCS(i, j-1) )
                return dp[i, j] 
            
        # -------------------------------------------------
        
        # Original s as text1
        text1 = s
        
        # Reversed s as text2
        text2 = s[::-1]
        
        # Longest palindromic subsequence of s = Longest common subsequence(s, s[::-1])
        return LCS( len(text1)-1, len(text2)-1 )

複雜度分析

令s的長度為n

時間複雜度:O(n^2)

二維DP，兩個維度的的遞迴，從字串的尾巴開始逆推回空字串，
更新最長共同(回文)子序列的長度。

空間複雜度:O(n^2)

二維DP，DP table總共紀錄O(n^2)個DP state的解。

關鍵知識點 LCS + 回文結構

利用化簡的技巧，發現彼此結構相同，把這題化簡到已經會解的Longest Common Subsequence

因為字串s 和 s逆序找出來的共同子序列的順序，剛好一左一右，前後顛倒，內容相等。

進而保障s 和 s逆序 找到的共同子序列一定是回文子序列，

推理出 s 和 s逆序 最長的共同子序列也一定是最長回文子序列

字串s 和 s逆序 最長的共同子序列

= LCS(s, s[::-1]) = LPS(s) = 字串s的最長回文子序列

Reference

[1] Longest Palindromic Subsequence - LeetCode

回到DP特訓班目錄 和 學習路徑