題目出處
1143. Longest Common Subsequence
難度
medium
個人範例程式碼
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
m, n = len(text1), len(text2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1 # same case, update value form text[i-1][j-1]
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) # default update
return dp[-1][-1]
算法說明
經典的 LCS 問題，我們建表來進行搜索，
表格更新的邏輯為：
input handling
一同在 dp 內處理。
Boundary conditions
用兩層 for 迴圈來控制範圍