題目連結:
題目意譯:
給定兩字串 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。
解題思維:
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。