https://leetcode.com/problems/longest-common-subsequence/
1143. Longest Common Subsequence
給你兩個字串，找出兩者的最長子序列，無則回傳0
僅可透過刪除原字串的字符形成新字串
不可改變剩餘字符的相對順序
Example 1:
Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.
Example 2:
Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.
Example 3:
Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.
思路:
LCS算法:
先將兩字串首字符拆分出來
s1 = s1+e1
s2 = s2+e2
lcs(e1,e2)
我們可區分四種狀況:
e1,e2在s1,s2之中 = lcs(sub1,sub2)+e1
e1,e2不在s1,s2之中 = lcs(sub1,sub2)
e1在s1,s2之中，e2則否 = lcs(e1,sub2)
e2在s1,s2之中,e1則否 = lcs(sub1,e2)
綜合四種狀況:
max(lcs(sub1,sub2),lcs(e1,sub2),lcs(sub1,e2))
lcs(sub1,sub2)+e1
= lcs(s1,s2)
再簡化:
max(lcs(sub1,sub2),lcs(e1,sub2))
lcs(sub1,sub2)+e1
= lcs(s1,s2)
Python3 code:
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
m = len(text1)
n = len(text2)
@cache
def lcs(i,j):
nonlocal m,n
if i >= m or j >= n:
return 0
if text1[i] == text2[j]:
return 1+lcs(i+1,j+1)
else:
return max(lcs(i+1,j),lcs(i,j+1))
return lcs(0,0)
這題應該要用dp
但我dp還是不太熟 偷吃步過關
等等回去再翻一下書