題目資訊

• 題目編號: 1143
• 題目連結: Longest Common Subsequence
• 主題: String, Dynamic Programming

題目敘述

給定兩個字串 text1 和 text2，返回它們的最長公共子序列的長度。如果不存在公共子序列，則返回 0。

字串的子序列是從原始字串中刪除某些字元（可以不刪除）後生成的新字串，但不改變剩餘字元的相對順序。

• 例如，"ace" 是 "abcde" 的子序列。

兩個字串的公共子序列是兩者共有的子序列。

範例 1:

輸入: text1 = "abcde", text2 = "ace" 
輸出: 3  
解釋: 最長公共子序列是 "ace"，其長度為 3。

範例 2:

輸入: text1 = "abc", text2 = "abc"
輸出: 3
解釋: 最長公共子序列是 "abc"，其長度為 3。

範例 3:

輸入: text1 = "abc", text2 = "def"
輸出: 0
解釋: 沒有這樣的公共子序列，所以結果為 0。

約束條件:

• $1 \leq \text{text1.length}, \text{text2.length} \leq 1000$
• text1 和 text2 只包含小寫英文字母。

直覺

在兩個字串中尋找最長公共子序列（LCS）的問題是一個經典問題，通常用動態規劃來解決。其主要思想是將問題分解為可以遞迴求解的小問題。我最初的想法是利用子序列的特性並使用一個二維動態規劃表來系統化地評估可能的子序列並存儲中間結果。這可以通過避免冗餘計算來提高計算效率。

解法

這個方法使用動態規劃來找出兩個字串 text1 和 text2 之間的最長公共子序列的長度。這一方法的核心是建立一個二維陣列 dp，其中 dp[i][j] 儲存子字串 text1[0...i-1] 和 text2[0...j-1] 的最長公共子序列的長度。

1. 初始化: 我們初始化一個大小為 (n+1) x (m+1) 的二維陣列 dp，其中 n 是 text1 的長度，m 是 text2 的長度。每個位置的初始值均為零。額外的一行和一列（從索引0開始）使得我們可以輕鬆處理基礎情況。

2. 迭代: 我們通過索引 i 遍歷 text1 中的每個字符，並通過索引 j 遍歷 text2 中的每個字符。對於每一對字符 (text1[i], text2[j])，我們根據以下情況更新 dp 表：

   • 如果字符 text1[i] 和 text2[j] 匹配，這意味著它們可以成為一個公共子序列的一部分。因此，我們可以通過增加這些字符來擴展之前找到的公共子序列。因此，dp[i+1][j+1] = dp[i][j] + 1。
   • 如果字符不匹配，則在這一點上的最長公共子序列可能排除 text1[i] 或 text2[j]。因此，我們取考慮任一子問題的最大值，dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])。

3. 結果: 填滿 dp 表後，所需的最長公共子序列的長度將位於 dp[n][m]。

這個方法的時間複雜度為 $O(n \times m)$，因為需要雙重循環遍歷兩個字串的字符，且空間複雜度也是 $O(n \times m)$，由於需要儲存 dp 表。鑒於約束條件，這是一個高效而可行的方法。

程式碼

C++

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        // 建立一個二維DP陣列並初始化為0
        vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));

        // 遍歷兩個字串中的每一個字元
        for (int i = 0; i < text1.size(); i++) {
            for (int j = 0; j < text2.size(); j++) {
                // 如果字元匹配，增加公共子序列的長度
                if (text1[i] == text2[j]) {
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                } else {
                    // 否則，傳遞目前為止發現的最大長度
                    dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
                }
            }
        }

        // 返回最長公共子序列的長度
        return dp[text1.size()][text2.size()];
    }
};

Python

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        # 創建一個二維DP陣列並初始化為0
        dp = [[0] * (len(text2) + 1) for _ in range(len(text1) + 1)]

        # 遍歷兩字串的每個字符
        for i in range(len(text1)):
            for j in range(len(text2)):
                # 如果字符匹配，增加公共子序列的長度
                if text1[i] == text2[j]:
                    dp[i + 1][j + 1] = dp[i][j] + 1
                else:
                    # 否則，沿用目前找到的最大長度
                    dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])

        # 返回最長公共子序列的長度
        return dp[len(text1)][len(text2)]

複雜度分析

• 時間複雜度: 算法的時間複雜度是 $O(m \times n)$，其中 $m$ 是 text1 的長度，$n$ 是 text2 的長度。這是因為該算法使用了巢狀迴圈來逐一遍歷兩個字串中的每個字符，導致 $m \times n$ 次迭代。

• 空間複雜度: 算法的空間複雜度是 $O(m \times n)$。該算法創建了一個大小為 $(m + 1) \times (n + 1)$ 的二維動態規劃（DP）陣列 dp 來存儲各個點的共同子序列長度。因此，所需的空間與輸入字串長度的乘積成正比。