今天來多刷點題目好了，明天來講更多經典題！有題能刷直須刷，莫待無題空寫扣。這些內容應該都是前幾天提過的，所以就當作刷習題的感覺來做吧。

Example 12: Leetcode 115 - Distinct Subsequences

題目連結

https://leetcode.com/problems/distinct-subsequences/

題目敘述

給你兩個字串 S 和 T，請問 S 有多少個子序列與 T 相同呢？

解題思考

這題其實就是問你把 T 的每一個字元按照順序安置(align)到 S，有幾種安置方法。

考慮到 S 字串和 T 字串的最後一個字元 S[n-1] 和 T[m-1]。如果它們不同，顯然 S 的最後一個字元完全用不到。因此 T 出現在 S 子序列的方法數，與 T 出現在 S[0..n-2] 這個前綴的方法數相同。相反地，如果 S[n-1] 與 T[m-1] 相同，那麼 T 的最後一個字元可以與之配對、或不與之配對形成了兩種情形。因此只要把這兩種情形對應的子問題加起來就得到答案囉。

參考程式碼 (Python3)

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        n, m = len(s), len(t)
        dp = [[0] * (m+1) for _ in range(n+1)]
        dp[0][0] = 1
        for i in range(1, n+1):
            dp[i][0] = 1
            for j in range(1, m+1):
                if s[i-1] != t[j-1]:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
        return dp[n][m]

Example 13: Leetcode 72 - Edit Distance

題目連結

https://leetcode.com/problems/edit-distance/

題目敘述

給你兩個字串 word1, word2。每一次可以插入、刪除、修改一個字元。請問至少要幾次操作才能將 word1 換成 word2 呢？

解題思考

這題跟 LCS 真的很像，只不過目標函數的最佳化方向是相反的，因此答案跟直接找 LCS 可能也略有出入。我們一樣關注於兩個字串的最後一個字元，如果最後一個字元相同，那麼所需要的最小 edit distance 一定來自於把該字元同時踢掉後的最小操作數。如果最後一個字元相異，那麼根據插入、刪除與取代（修改）三種操作分別會對應到三個不同的狀態。擇其最小花費加上 1 個額外操作就可以完成囉～

參考程式碼 (Python3)

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        n, m = len(word1), len(word2)
        dp = [list(range(i, m+i+1)) for i in range(n+1)]
        for i in range(1, n+1):
            for j in range(1, m+1):
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
        return dp[n][m]

值得一提的是初始條件。在這邊我們很偷懶地使用一行初始值：對於陣列足標 (i, j)，代表 word1 前 i 個字元與 word2 前 j 個字元。我們直接用 i+j 代表其初始值。事實上這個值是把 word1[1~i] 修改成 word2[1~j] 的操作數的高估（在程式碼中間也不太需要他），只有在邊界的地方 (i=0, j=0) 是準的。

Example 14: Leetcode 516 - Longest Palindromic Subsequence

題目連結

https://leetcode.com/problems/longest-palindromic-subsequence/

題目敘述

給你一個字串，請找出最長的迴文子序列。

解題思考

這題有兩種有趣的解題思路唷。第一種是直接作：考慮 S[i~j] 這個子字串，如果 S[i] = S[j]，那麼其最長迴文子序列一定來自 S[i+1~j-1] 的最長迴文子序列長度 + 2（總可以在答案外面加上兩個字元 S[i] 和 S[j] 以後仍然是迴文）。如果 S[i] ≠ S[j]，那麼其最長迴文子序列一定不會同時包含S[i] 和 S[j]。因此答案會是 S[i+1~j] 或 S[i~j-1] 其中一個的最長迴文子序列。

第二種比較有趣，第二種是直接宣稱答案是 LCS(S, reverse(S))。證明可以用反證法證明。反正就是對的！

參考程式碼 (Python3)

class Solution:
    def longestCommonSubsequence(self, s: str, t: str) -> int:
        n, m = len(s), len(t)
        dp = [0] * (m+1)
        for i in range(1, n+1):
            nxt = [0] * (m+1)
            for j in range(1, m+1):
                if s[i-1] == t[j-1]:
                    nxt[j] = dp[j-1] + 1
                else:
                    nxt[j] = max(dp[j], nxt[j-1])
            dp = nxt
        return dp[m]
    
    def longestPalindromeSubseq(self, s: str) -> int:
        t = s[::-1]
        return self.longestCommonSubsequence(s, t)

上面這個寫法是逐行回收記憶體使用的。感覺他抓時間沒有抓很準耶，如果一次開太大陣列的時候記憶體回收時間會飄來飄去，使用 Python 會更容易 TLE 的樣子。比方說原本開個二維陣列，最內側迴圈可以用一行完成更新：

dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1] + (1 if s[i-1] == t[j-1] else 0))

但執行起來就超過時間了。

經典部分：找出一條實際的 LCS

要怎麼找出一條實際的 LCS 呢？其實都已經有 DP 表格了，沿著 DP 表格的右下角，根據每個格子是怎麼計算出來的，一路回溯就可以找出整條 LCS 了唷。值得一提的是，這個方法時間複雜度與空間複雜度都是 O(MN)。實際上 1975 年由 Dan Hirschberg （現在為 UC Irvine 教授，發表論文的當時他是 Princeton University 的研究生）提出了一個精妙的分而治之的方法、在 O(MN) 時間複雜度與線性 O(M+N) 的空間複雜度的條件之下找出一條 LCS 的解。

有興趣的朋友可以參考 https://en.wikipedia.org/wiki/Hirschberg's_algorithm 這個介紹。

既然只是刷題，我們就用最簡單的方式把題目刷出來吧：

Example 15: Leetcode 1092 - Shortest Common Supersequence

題目連結

https://leetcode.com/problems/shortest-common-supersequence/

題目敘述

給你兩個字串 str1 與 str2，找出一個最短的公共字串 S，使得 str1 與 str2 同時是 S 的子字串。

解題思考

其實這個公共字串的長度就是 len(str1) + len(str2) - |LCS(str1, str2)|。因此我們要思考的方向是先做出 LCS 表格以後，如何利用 LCS 表格回溯出一個可行的 S。其實也很單純：如果末端兩個字元一樣，就把該字元加回 S，如果不一樣，看砍掉哪一邊剩下 LCS 比較長，就優先把那邊加回 S。

參考程式碼 (Python3)

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        n, m = len(str1), len(str2)
        dp = [[0] * (m+1) for _ in range(n+1)]
        for i in range(1, n+1):
            for j in range(1, m+1):
                if str1[i-1] == str2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        
        answer = ""
        i, j = n, m
        while i > 0 and j > 0:
            if str1[i-1] == str2[j-1]:
                answer += str1[i-1]
                i, j = i-1, j-1
            elif dp[i-1][j] > dp[i][j-1]:
                answer += str1[i-1]
                i = i-1
            else:
                answer += str2[j-1]
                j = j-1
        answer = answer[::-1]
        return str1[0:i] + str2[0:j] + answer