前往
大廳
主題

LeetCode - 1143. Longest Common Subsequence 解題心得

Not In My Back Yard | 2022-03-14 00:00:09 | 巴幣 0 | 人氣 258

題目連結:


題目意譯:
給定兩字串 text1 和 text1,回傳它們的最長共同子序列(Longest Common Subsequence,LCS)之長度。如果沒有共同子序列的話,回傳 0。

一個字串的一個子序列為一個新的字串其由刪除原字串若干個(可能沒有)字元並且不更動剩餘字串的相對順序而得到。

例如,"ace" 為 "abcde" 的一個子序列。
兩個字串的一個共同子序列為一子序列其為兩字串所共有的。

限制:
1 ≦ text1.length, text2.length ≦ 1000
text1 和 text2 只由小寫英文字母組成。


範例測資:
範例 1:
輸入: text1 = "abcde", text2 = "ace"
輸出: 3  
解釋: 最長共同子序列為 "ace" 且其長度為 3。

範例 2:
輸入: text1 = "abc", text2 = "abc"
輸出: 3
解釋: 最長共同子序列為 "abc" 且其長度為 3。

範例 3:
輸入: text1 = "abc", text2 = "def"
輸出: 0
解釋: 沒有最長共同子序列,因此結果為 0。


解題思維:
典型的 LCS 題型,參見這題的解法。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作