Re: [閒聊] 每日LeetCode已回收

看板Marginalman作者sustainer123 (caster )時間1年前 (2024/01/25 21:56)推噓5(5推 0噓 0→)

留言5則, 5人參與討論串619/719 (看更多)

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

推

SecondRun

01/25 21:57, 1年前 , 1^F

01/25 21:57, 1^F

推

JIWP

01/25 21:58, 1年前 , 2^F

01/25 21:58, 2^F

推

NTUEE2CS

01/25 22:01, 1年前 , 3^F

01/25 22:01, 3^F