###### tags: `阿瑜` # Day 17: LeetCode 1143. Longest Common Subsequence ## Source https://leetcode.com/problems/longest-common-subsequence/ ### 1.題意: 經典題: 找最長的共同子序列。 ### 2.思路: - 待圖解 ### 3.程式碼: ```python3 class Solution: def longestCommonSubsequence(self, text1: str, text2: str) -> int: len1 = len(text1) # abcde(5) -- row len2 = len(text2) # ace(3) -- col R = [[0 for _ in range(len2+1)] for _ in range(len1+1)] #print(R) ''' for i in range(len1+1): for j in range(len2+1): print(R[i][j],end="") print() ''' # len1: row # len2: col for i in range(len1+1): for j in range(len2+1): if i==0 or j==0: R[i][j] = 0 elif text1[i-1]==text2[j-1]: #R-i:text-(i-1),R-j:text-(j-1) R[i][j] = R[i-1][j-1]+1 #左上位置的值+1 else: R[i][j] = max(R[i-1][j],R[i][j-1]) #上一row同一col vs 上一col同一row 取大 #print(R) return R[len1][len2] ``` #### Result 待優化 ### 補充 > R = [[0 for _ in range(col+1)] for _ in range(row+1)] 建立row+1個列 col+1個行 - [如何在 Python 中建立二維陣列](https://www.delftstack.com/zh-tw/howto/python/how-to-initiate-2-d-array-in-python/) #### 參考 1. https://leetcode.com/problems/longest-common-subsequence/discuss/436719/Python-very-detailed-solution-with-explanation-and-walkthrough-step-by-step 2. https://www.geeksforgeeks.org/longest-common-subsequence-dp-4/ - https://www.youtube.com/watch?v=HgUOWB0StNE