我要來還 2016 跟自己欠下的債囉，幸好無利息XD

起因是最近寫了一點跟字串比對有關的 Leetcode 題目，大多都會用 DP 去解，除了迴文系列的題型，可以考慮用很酷的演算法，比如我分享過的 Manacher 演算法，在兩個字串比對的題目，大家直覺上還是會先採納 DFS 或是 DP 的方式

在寫完 Leetcode 1143 後，就想到我之前有一篇紀錄 Coursera 演算法課程的舊文: Edit Distance 最小編輯距離有提到 LCS

當時我應該是在忙實習，來不及解 LCS 的作業，所以沒有很詳細的理解並記錄兩個字串之間的動態規劃怎麼做的，欠了知識債沒還結果到現在重頭來過了哈哈

題目

在給定的兩個字串中(長度不一定一樣)，找出最長的共同子序列的長度

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.

動態規劃分析

在使用 DP 的時候，要先定義陣列應該要有的初始狀態與更新陣列的條件

更新陣列數值的條件是最難的部分(我覺得)，因為我一開始剛接觸 DP 時真的沒辦法馬上掌握怎麼去看出條件，現在還不敢說掌握得很好，還是有參考網路上的解釋，然後自己真的理解一遍

這題跟在同個字串中找迴文的題目們不一樣的地方是，我們要比對的是兩個不一樣長的字串，所以在二維陣列中的每一格都要被考量進去，而每一格放的值就是累積起來的最長共同子序列的長度

這類型的字串 DP，使用二維陣列去分析子問題時，會發現有個明顯的 pattern

在每個 (i, j) 的位置上，我們會考慮他的周圍三個鄰居，根據題目目的的不同，可能是考慮左上、上、左，或是左上、下、左，如圖所示

這題我們需要考慮所有位置，不會有在對角線先填入數值的步驟，而是需要將第一行與第一列先填入 0 進行初始化，讓一開始的計算能夠有鄰居的值能參考，如下圖所示，

從分析子問題開始，這題要問的是長度，所以我們可以從相同子序列的長度小到大開始分析

因為會有兩個字串，我們先固定 text2 = “abcd”，讓 text1 變動來觀察

分析子問題

長度 1 的情況

假設 text2 = “a”

二維陣列的擺放，看個人想怎麼決定 row & col，這邊我是以 text1 為 col，text2 為 row

所以 matrix[i][j] 代表的就會是，text1 (0~j) 的字串與 text2 (0~i) 的字串

1
2
3
4
matrix[1][1] = "a" vs "a" => 1
matrix[2][1] = "ab" vs "a" => 1
matrix[3][1] = "abc" vs "a" => 1
matrix[4][1] = "abcd" vs "a" => 1

長度 2 的情況

假設 text1 = “ab”

1
2
3
4
5
6
7
8
9
matrix[1][1] = "a" vs "a" = 1 => t2[i - 1] == t1[j - 1]
matrix[2][1] = "ab" vs "a" = 1 => t2[i - 1] != t1[j - 1]
matrix[3][1] = "abc" vs "a" = 1 => t2[i - 1] != t1[j -1]
matrix[4][1] = "abcd" vs "a" = 1 => t2[i - 1] != t1[j - 1]

matrix[1][2] = "a" vs "ab" = 1 => t2[i - 1] != t1[j - 1]
matrix[2][2] = "ab" vs "ab" = 2 => t2[i - 1] == t1[j - 1]
matrix[3][2] = "abc" vs "ab" = 2 => t2[i - 1] != t1[j - 1]
matrix[4][2] = "abcd" vs "ab" = 2 => t2[i - 1] != t1[j - 1]

由上述觀察 i, j 的位置在 t1, t2 所指到的字元一樣與不一樣的情形

1
2
3
4
5
6
7
8
9
10
matrix[4][2] = "abcd" vs "ab" = 2 
因為 t2[i - 1] != t1[j - 1]

所以我們得參考前面已經有的結果，取最大的

我們可以把，"abcd" 與 "ab" 做拆解來看
"abcd" vs "a"
"abc" vs "ab"

就是 Max(matrix[4][1], matrix[3][2])
1
2
3
4
5
6
7
8
9
10
matrix[2][2] = "ab" vs "ab"
這時 t2[i - 1] == t1[j - 1]

所以我們可以判定共同子序列的長度會 +1

然後還需要考慮累加，所以要回去考慮這兩個字串分別減少一個字元(也就是當前的字元)後的長度

"a" vs "a" => matrix[1][1]

所以完整的結果是 matrix[i - 1][j - 1] + 1

由上面的分析就可以推導出

1
2
3
4
if t1[j - 1] == t2[i - 1]
  matrix[i][j] = matrix[i - 1][j - 1] + 1
else
  matrix[i][j] = Max(matrix[i][j - 1], matrix[i - 1][j])

二維陣列的初始條件與更新條件都完成，就可以開始建構 DP table 了

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        // DP solution, matrix to record the length
        int n = text1.length();
        int m = text2.length();
        
        // Extend one more row and column since we're comparing two different strings
        // that will need to calculate every position in the matrix.
        // Every position need its neighbors to calculate the length.
        int matrix[][] = new int[m + 1][n + 1];
        
        // Set first row and first column to 0 for initialize which represent the empty string
        for (int i = 0; i <= n; i++) {
            matrix[0][i] = 0;
        }
        for (int i = 0; i <= m; i++) {
            matrix[i][0] = 0;
        }
        
        int maxLen = 0;
        // from left to right, top to bottom
        for (int col = 1; col <= n; col++) {
            for (int row = 1; row <= m; row++){
                if (text1.charAt(col - 1) == text2.charAt(row - 1)) {
                    matrix[row][col] = matrix[row - 1][col - 1] + 1;
                } else {
                    matrix[row][col] = Math.max(matrix[row][col - 1], matrix[row - 1][col]);
                }
                maxLen = Math.max(maxLen, matrix[row][col]);
            }
        }
        return maxLen;
    }
}

最後我們根據表格就能得出共同最長的子序列長度

複雜度

時間複雜度：$O(N^2)$

空間複雜度：$O(N)$

這題應有速度更快的做法，這裡我只是單純想還幾年前說要寫筆記的債

再次證明當下偷懶，以後還是得補回來 OTZ