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还是不太熟 偷吃步过关
等等回去再翻一下书