推 SecondRun: 大師 01/25 21:57
推 JIWP: 大師 01/25 21:58
推 NTUEE2CS: 好懷念 以前演算法作業 這題難點是要用dfs還是bfs 01/25 22:01
推 digua: 大師 01/25 22:02
推 JerryChungYC: 想了半天解不出來 我就這樣了 01/25 23:46
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還是不太熟 偷吃步過關
等等回去再翻一下書
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.137.49.59 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1706190996.A.C2A.html