LeetCode 筆記 - 1143. Longest Common Subsequence

題目在此 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]

也許你也會想看看