從LeetCode學演算法 - 95 Dynamic Programming (12)

1143. Longest Common Subsequence (Medium)

寫在前面

容筆者工商一下，
接下來**「從Leetcode學演算法｜進階篇」** 即將於6/9 開放預購啦！
這次選了40道難度加深的LeetCode題目，
同樣也會細部解說對應的技巧及須要掌握的演算法！
同時這次購買進階篇的話，
額外還加贈**「從Leetcode學演算法｜面試篇」** ！
當中包含了面試準備須知分享，及訪談國內外不同經驗的工程師 ，
讓你不論是想走前端/後端/一般軟工 或者是想找國外的工作 ，
是初學想轉職 還是正在工作 ，都能夠從中得到收穫呦！
有興趣的朋友請留意下一篇貼文的早鳥優惠～

另外，

Question

Given two strings text1 and text2, return the length of their longest common subsequence.

A subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, “ace” is a subsequence of “abcde” while “aec” is not). A common subsequence of two strings is a subsequence that is common to both strings.

If there is no common subsequence, return 0.

Example 1

1
2
3
Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2

1
2
3
Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3

1
2
3
Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

Constraints

1 <= text1.length <= 1000
1 <= text2.length <= 1000
The input strings consist of lowercase English characters only.

分析/解題

給定兩個字串text1及text2，
回傳他們的最長共同子序列(Logest Common Subsequence, LCS)。
一個字串的子序列是指一個字串從字串中原始的一些字母得來，
當中刪去原字串的一些字元(也可以都不刪)，
但保持相對於在原字串中的排列順序。
舉例來說 ，”ace ”是**”a** bc de” 的子序列，但”ae c”不是。
(排列相對順序已經不一樣了)
兩個字串的共同子序列是指這個字串分別都是兩個字串的子序列。

如果沒有共同子序列，則回傳0。

當我們看到題目乍看之下沒有明顯的簡單解法時，
就要考慮一下先找出前後之間的關聯 。
也就是說，
我們要先考慮從某一步推往下一步的算式。

由於我們要求的是LCS，這個要求對應順序的特性，
會導致一點：
前面經過的字母，後面就不能用了。 比方說"abec drr"跟”ac e”，假設我們已經找到了 a 跟 c ，
接下來我們只會從”drr”跟”e”之間作找尋，
因為"abec"中的 e 沒辦法跟第二個字串對應(順序會亂掉)。
這也表示，分別對兩個字串取出兩個子字串的LCS，
只會跟它們更前面的部分有關聯 ，而和後面的字元沒有關係。
思考到這裡，顯然這極有可能是Dynamic Programming了XD

那麼，我們不妨將t1和t2兩個子字串的記法用 i 和 j 表示，
當中0代表完全空字串，最大則分別到l1, l2。
(也就是i, j就代表現在在t1, t2的第幾個字元，從1開始 )
我們假設每個值互相關聯，那麼可以寫成一個二維陣列或串列dp。
所以我們知道dp[0][0] == dp[i][0] == dp[0][j] == 0。
(因為至少有一邊是空字串)
下一步呢？
如果我們在分別取 i, j 的字元數，那麼會分兩種狀況：
1. t1[i-1] == t2[j-1] (i, j 的位置上的字元一模一樣)
=> dp[i][j] = dp[i-1][j-1] + 1 因為對應的位置上得到相同字元，所以可以納入子序列中，
所以假設我們知道dp[i-1][j-1]，那麼dp[i][j]應該就恰好多1。

*這邊很容易搞混，請留意因為計算 index 的時候是從0 開始，
所以我們的dp[i][j] 指的是比較 t1 的 0 到 i-1 及 ** t2** 的 ** 0 到 j-1兩個子字串。**

2. i, j位置上的字元不同 => 往回推一個字元
由於i, j上的字元不同，所以dp[i][j]要嘛和dp[i][j-1]相同，
要嘛和dp[i-1][j]相同。也就是說，兩個子字串其中一個 往回退一格所得到的結果，
當中取比較大 的就可以了。(因為我們在找最大的解嘛XD)

為什麼不能同時退？
因為可能一邊對到的是前一個阿！
比方說：
“a bce ffz”跟”ac rrre”，假設我們現在正在比較”abcef”跟”acrrre”，
由於f和e不一樣，所以我們要改成比較"abce “-”acrrre ”和”abcef ”-”acrrr ”。
如果我們直接各退一格，去比較”abce”跟"acrrr”，
那e的對應不就被我們去掉了嗎？所以顯然要去除掉沒有對應到的字元，
一次只能從其中一邊倒退一格才行。

按照這個方式，我們可以使用雙層的迴圈，
就可以將整個dp陣列或串列算完，最終dp[l1][l2]就會是我們想要的答案。

回顧一下，我們利用了順序必須不變 的特性，
確定了某個位置的值只跟前面的結果 有關；
接著，判定當下對到的字元是否相同 ，
相同的話 可以計入並用各自的前一格 的結果表示，
不同的話 則要看誰退一格比較好 。
因此所有的值彼此環環相扣，某個位置的值可以用前面的位置的值來表達，
所以這的確是動態規劃 的問題無誤。

依此，寫成程式碼如下：

Java

Java的部分除了要留意index的計算不要搞錯以外，
整個程式碼相當簡單。

Python

Python的部分不要忘記二維串列不要連續用 * 的方式，
(記憶體使用會重疊而不是開新的串列，這個之前有提到過)
其他基本一模一樣。

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(l1 * l2), O(l1 * l2))

相似及延伸

這題依照不同的起始方式，解也有不同的寫法，
讀者可以嘗試看看有沒有別的寫法。
同時，讀者可能會發現只要前一層的數據，
就可以拿來算下一層了，那麼，儲存的空間可以再進行精簡，
請想想看，這樣子空間複雜度會變成多少呢？

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~

感謝大家對這系列文章的支持！這邊跟大家自我工商一下：

筆者開設的系列同名線上課程：
「從Leetcode學演算法｜基礎篇」已經快回原價啦！ 在這堂課中，你將學會利用十種演算法/資料結構來優化解題過程，
並實際完整練習20題 精選考古題，
進而逐漸提升到不需提示也可以突破白板題，取得工作門票！

想要一次全包的話，請等待下一篇貼文提供的同捆包 XD

如果不太確定這是不是你想要的，
底下是最後一波優惠連結(下次就回原價囉)： ** https://hiskio.com/courses/319?promo_code=VE9Q5VE**