題目

#

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 陣列，逐步填表計算最長公共子序列的長度。

解法

#

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

最終結果： 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”

完整程式碼

#

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)