題目
#

leetcode 1143 - Longest Common Subsequence (題目說明請點連結)

題目簡述
#

給兩個字串 text1 和 text2，請找出它們的最長公共子序列（Longest Common Subsequence, LCS）的長度。
子序列是指在不改變字符相對順序的情況下，刪除某些字符後得到的新字串。例如，“ace” 是 “abcde” 的子序列。

範例
#

Example 1:

Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: 最長公共子序列是 "ace"，長度為 3。

Example 2:

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: 最長公共子序列是 "abc"，長度為 3。

Example 3:

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: 沒有公共子序列，長度為 0。

解題思路
#

這題要求我們找出兩個字串的最長公共子序列（LCS）的長度。我們可以使用動態規劃（Dynamic Programming）來解決這個問題，具體方法是創建一個二維 DP 陣列，逐步填表計算最長公共子序列的長度。

解法
#

創建二維 DP 陣列 dp[m+1][n+1]，其中 dp[i][j] 表示 text1[0...i-1] 和 text2[0...j-1] 的最長公共子序列長度
初始化邊界條件：dp[0][j] = 0 和 dp[i][0] = 0
填表過程：根據字符是否相等來更新 DP 值
返回最終結果 dp[m][n]

步驟
#

初始化：
- 創建 (m+1) × (n+1) 的 DP 陣列
- 設定邊界條件：第一行和第一列為 0
填表過程：
- 遍歷 text1 和 text2 的每個字符
- 如果字符相等：dp[i][j] = dp[i-1][j-1] + 1
- 如果字符不相等：dp[i][j] = max(dp[i-1][j], dp[i][j-1])
返回結果：
- 返回 dp[m][n]，即最長公共子序列的長度

例子說明
#

text1 = "abcde", text2 = "ace"

步驟	i	j	text1[i-1]	text2[j-1]	是否相等	dp[i][j]	說明
初始化	-	-	-	-	-	邊界為 0	創建 DP 陣列
第 1 步	1	1	‘a’	‘a’	是	dp[0][0] + 1 = 1	字符相等，LCS 長度加 1
第 2 步	1	2	‘a’	‘c’	否	max(dp[0][2], dp[1][1]) = 1	字符不相等，取最大值
第 3 步	1	3	‘a’	’e'	否	max(dp[0][3], dp[1][2]) = 1	字符不相等，取最大值
第 4 步	2	1	‘b’	‘a’	否	max(dp[1][1], dp[2][0]) = 1	字符不相等，取最大值
第 5 步	2	2	‘b’	‘c’	否	max(dp[1][2], dp[2][1]) = 1	字符不相等，取最大值
第 6 步	2	3	‘b’	’e'	否	max(dp[1][3], dp[2][2]) = 1	字符不相等，取最大值
第 7 步	3	1	‘c’	‘a’	否	max(dp[2][1], dp[3][0]) = 1	字符不相等，取最大值
第 8 步	3	2	‘c’	‘c’	是	dp[2][1] + 1 = 2	字符相等，LCS 長度加 1
第 9 步	3	3	‘c’	’e'	否	max(dp[2][3], dp[3][2]) = 2	字符不相等，取最大值

最終結果： 3

DP 陣列填表過程說明：

dp[1][1] = 1：text1[0] = 'a' 和 text2[0] = 'a' 相等，LCS 長度為 1
dp[3][2] = 2：text1[2] = 'c' 和 text2[1] = 'c' 相等，加上之前的 LCS，總長度為 2
dp[5][3] = 3：text1[4] = 'e' 和 text2[2] = 'e' 相等，加上之前的 LCS，總長度為 3

最長公共子序列： “ace”

完整程式碼
#

java

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        // 獲取兩個字串的長度
        int m = text1.length();
        int n = text2.length();

        // 創建 DP 陣列，dp[i][j] 表示 text1[0...i-1] 和 text2[0...j-1] 的 LCS 長度
        int[][] dp = new int[m + 1][n + 1];

        // 填表過程：遍歷兩個字串的每個字符
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(text1.charAt(i - 1) == text2.charAt(j - 1)){
                    // 如果當前字符相等，LCS 長度加 1
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    // 如果當前字符不相等，取左邊或上邊的最大值
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        // 返回最長公共子序列的長度
        return dp[m][n];
    }
}

時間複雜度
#

時間複雜度：O(m × n)，其中 m 和 n 是兩個字串的長度
- 需要填滿整個 DP 陣列：O(m × n)
- 每個位置需要常數時間的計算
- 總時間複雜度為 O(m × n)
空間複雜度：O(m × n)
- 需要創建二維 DP 陣列：O(m × n)
- 其他變數使用常數空間：O(1)
- 總空間複雜度為 O(m × n)