LeetCode 筆記 - 1143. Longest Common Subsequence

Posted on

題目在此 1143. Longest Common Subsequence

給定兩個字串，請找出共同的子序列長度
例如：

Input: text1 = “abcde”, text2 = “ace”
Output: 3

解題思維

同學，這題是非常經典的問題 Longest Common Subsequence

對於任意數量的字串，是屬於 NP-Hard

如果是確定數量的字串，例如這次題目就是兩個字串
那就可以使用 Dynamic programming 在 O(N2) 時間之內解決

首先建立一張二維矩陣 dp[i][j] 紀錄 text1 i 位之前與 text2 j 位之前的 LCS 長度

所以如果 text1[i] == text2[j] 那麼 dp[i][j] = dp[i - 1][j - 1] + 1
不然就是 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) 直接延續之前的結果

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        
        size1 = len(text1)
        size2 = len(text2)
        
        dp = [[0 for _ in range(size2)] for _ in range(size1)]
        
        for i in range(size1):
            for j in range(size2):
                if text1[i] == text2[j]:
                    if i == 0 or j == 0:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        return dp[-1][-1]

相關文章