題目資訊

題目編號: 1092
題目連結: Shortest Common Supersequence
主題: String, Dynamic Programming

題目敘述

給定兩個字串 str1 和 str2，返回擁有 str1 和 str2 作為子序列的最短字串。如果有多個合法的字串，返回其中任何一個。

字串 s 是字串 t 的一個子序列，如果從 t 刪除某些字符（可能為 0 個）後得到字串 s。

範例 1:

輸入: str1 = "abac", str2 = "cab"
輸出: "cabac"
解釋: 
str1 = "abac" 是 "cabac" 的一個子序列，因為我們可以刪除第一個 "c"。
str2 = "cab" 是 "cabac" 的一個子序列，因為我們可以刪除最後的 "ac"。
提供的答案是滿足這些屬性的最短字串。

範例 2:

輸入: str1 = "aaaaaaaa", str2 = "aaaaaaaa"
輸出: "aaaaaaaa"

限制條件:

$1 \leq \text{str1.length}, \text{str2.length} \leq 1000$
str1 和 str2 由小寫英文字母組成。

直覺

本問題旨在尋找一個最短的字串，使得該字串同時包含給定的兩個字串作為子序列。需要注意的是，子序列不需要是連續的字符，但必須保持相對順序。此問題可聯想到序列比對中的公共祖先，概念上類似於最短公共超序列（Shortest Common Supersequence, SCS），其與最長公共子序列（Longest Common Subsequence, LCS）有密切關聯。透過確定LCS，我們可策略性地將兩個字串中不同的字符穿插於此序列周圍，以構成所需的SCS長度。

解法

解決此問題的方法採用動態規劃，構建一個表格，其中在索引 $(i, j)$ 的每個條目代表字串 str1 和 str2 在索引 $i$ 和 $j$ 之前的子字串的最短公共超序列的長度。

初始化：建立一個二維列表 dp，其維度為 $(\text{len1} + 1) \times (\text{len2} + 1)$，其中 len1 和 len2 為字串 str1 和 str2 的長度。初始化基本情況，當一個字串為空時：
- 當一個字串為空，SCS 直接等於另一字串的長度。因此，設 dp[i][0] = i 和 dp[0][j] = j。
動態規劃表格構建：
- 遍歷 str1 和 str2 的每個字符索引。
- 如果兩字串在當前位置的字符相同，則 dp[i][j] = dp[i-1][j-1] + 1，因為匹配的字符可直接貢獻至SCS。
- 如果字符不匹配，則 dp[i][j] = \min(dp[i-1][j], dp[i][j-1]) + 1，因為最佳的 SCS 包括需要較少字符刪除的那一方（str1 或 str2）。
重建最短公共超序列：
- 從 dp[len1][len2] 開始，依據 dp 迴溯構建 SCS。
- 如果字符匹配，則包括該字符並對角移動。
- 如果 dp[i][j-1] 導致當前單元格，則包括來自 str2 的字符。
- 如果 dp[i-1][j] 導致當前單元格，則包括來自 str1 的字符。
- 繼續直到其中一個字串完全遍歷，此時附加另一字串中剩餘的字符。

遵循上述程序，效率地構建了最短公共超序列，且此序列既包含兩個輸入字串作為子序列。

程式碼

C++

class Solution {
public:
    string shortestCommonSupersequence(string str1, string str2) {
        int len1 = str1.size();
        int len2 = str2.size();
        vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1));
        
        // 初始化基本情況：當其中一個字串為空時的最短共同超序列長度。
        for (int i = 0; i <= len1; i++) dp[i][0] = i;
        for (int j = 0; j <= len2; j++) dp[0][j] = j;
        
        // 構建 dp 表，dp[i][j] 表示
        // 子字串 str1[0...i-1] 和 str2[0...j-1] 的最短共同超序列的長度。
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (str1[i - 1] == str2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
                }
            }
        }

        // 使用 dp 表重建最短共同超序列。
        int curIndex1 = len1;
        int curIndex2 = len2;
        string result = "";

        while (curIndex1 != 0 || curIndex2 != 0) {
            if (curIndex2 == 0) {
                result = str1[--curIndex1] + result;
            } else if (curIndex1 == 0) {
                result = str2[--curIndex2] + result;
            } else if (dp[curIndex1 - 1][curIndex2 - 1] == dp[curIndex1][curIndex2] - 1 && str1[curIndex1 - 1] == str2[curIndex2 - 1]) {
                result = str1[--curIndex1] + result;
                --curIndex2;
            } else if (dp[curIndex1][curIndex2 - 1] == dp[curIndex1][curIndex2] - 1) {
                result = str2[--curIndex2] + result;
            } else {
                result = str1[--curIndex1] + result;
            }
        }

        return result;
    }
};

Python

class Solution:
    def shortestCommonSupersequence(self, str1, str2):
        len1 = len(str1)
        len2 = len(str2)
        dp = [[0] * (len2 + 1) for _ in range(len1 + 1)]
        
        # 初始化基準情況：如果有一個字串為空，則超序列的長度
        for i in range(len1 + 1):
            dp[i][0] = i
        for j in range(len2 + 1):
            dp[0][j] = j
        
        # 建立 dp 表格，其中 dp[i][j] 表示子字串 
        # str1[0...i-1] 與 str2[0...j-1] 的最短公共超序列的長度。
        for i in range(1, len1 + 1):
            for j in range(1, len2 + 1):
                if str1[i - 1] == str2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1

        # 使用 dp 表重建最短公共超序列。
        curIndex1 = len1
        curIndex2 = len2
        result = ""

        while curIndex1 != 0 or curIndex2 != 0:
            if curIndex2 == 0:
                result = str1[curIndex1 - 1] + result
                curIndex1 -= 1
            elif curIndex1 == 0:
                result = str2[curIndex2 - 1] + result
                curIndex2 -= 1
            elif dp[curIndex1 - 1][curIndex2 - 1] == dp[curIndex1][curIndex2] - 1 and str1[curIndex1 - 1] == str2[curIndex2 - 1]:
                result = str1[curIndex1 - 1] + result
                curIndex1 -= 1
                curIndex2 -= 1
            elif dp[curIndex1][curIndex2 - 1] == dp[curIndex1][curIndex2] - 1:
                result = str2[curIndex2 - 1] + result
                curIndex2 -= 1
            else:
                result = str1[curIndex1 - 1] + result
                curIndex1 -= 1

        return result

複雜度分析

時間複雜度：時間複雜度為 $O(\text{len1} \times \text{len2})$，其中 $\text{len1}$ 和 $\text{len2}$ 分別是 str1 和 str2 的長度。解決方案構建了一個動態規劃表格 (dp)，其維度為 $(\text{len1} + 1) \times (\text{len2} + 1)$。建立表格和重構最短公共超序列的過程都需要 $O(\text{len1} \times \text{len2})$ 的時間。
空間複雜度：空間複雜度為 $O(\text{len1} \times \text{len2})$。這空間用於維護 dp 表格，以存儲 str1 和 str2 所有可能子字符串的最短公共超序列的長度。

CS Note
En

Leetcode 1092. Shortest Common Supersequence

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析