Hard

题目描述

给出两个字符串 str1 和 str2，返回同时以 str1 和 str2 作为子序列的最短字符串。如果有多个有效的最短超序列，返回任意一个即可。

字符串 s 是字符串 t 的子序列是指，通过删除字符串 t 中的某些字符（可以不删除）后能得到字符串 s。

示例 1：

输入：str1 = "abac", str2 = "cab"
输出："cabac"
解释：
str1 = "abac" 是 "cabac" 的子序列，因为我们可以删除第一个 "c" 得到 "abac"。 
str2 = "cab" 是 "cabac" 的子序列，因为我们可以删除最后的 "ac" 得到 "cab"。
最终答案是满足这些属性的最短的字符串。

示例 2：

输入：str1 = "aaaaaaaa", str2 = "aaaaaaaa"
输出："aaaaaaaa"

约束条件：

  • 1 <= str1.length, str2.length <= 1000
  • str1 和 str2 都只包含小写英文字母

提示：

  • 可以使用动态规划找到 str1[i:] 和 str2[j:] 之间最长公共子序列的长度（对于所有的 (i, j)）
  • 可以使用这个信息来恢复最短公共超序列

解题思路

解题思路

这道题目要求找到包含两个字符串作为子序列的最短超序列。核心思路是利用最长公共子序列（LCS）来构建答案。

基本思想：

  1. 最短公共超序列的长度 = len(str1) + len(str2) - LCS_length
  2. 通过动态规划找到LCS，同时记录构造路径
  3. 按照LCS的构造路径来组合两个字符串

算法步骤：

  1. 构建LCS的DP表：使用二维数组dp[i][j]表示str1[0:i]和str2[0:j]的最长公共子序列长度
  2. 回溯构造超序列：从dp[m][n]开始，根据DP转移关系反向构造：
    • 如果str1[i-1] == str2[j-1]，说明这个字符在LCS中，只添加一次
    • 如果dp[i-1][j] > dp[i][j-1]，说明LCS来自于str1[i-1]，添加这个字符
    • 否则LCS来自于str2[j-1]，添加这个字符
  3. 处理剩余字符：将还未处理的字符依次添加到结果中

这种方法保证了构造出的超序列是最短的，因为它最大化利用了两个字符串的公共部分。

时间复杂度：O(m×n)，其中m和n分别是两个字符串的长度
空间复杂度：O(m×n)，用于存储DP表

代码实现

class Solution {
public:
    string shortestCommonSupersequence(string str1, string str2) {
        int m = str1.length(), n = str2.length();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        
        // 构建LCS的DP表
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (str1[i-1] == str2[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        
        // 回溯构造超序列
        string result = "";
        int i = m, j = n;
        while (i > 0 && j > 0) {
            if (str1[i-1] == str2[j-1]) {
                result = str1[i-1] + result;
                i--;
                j--;
            } else if (dp[i-1][j] > dp[i][j-1]) {
                result = str1[i-1] + result;
                i--;
            } else {
                result = str2[j-1] + result;
                j--;
            }
        }
        
        // 添加剩余字符
        while (i > 0) {
            result = str1[i-1] + result;
            i--;
        }
        while (j > 0) {
            result = str2[j-1] + result;
            j--;
        }
        
        return result;
    }
};

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        m, n = len(str1), len(str2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        
        # 构建LCS的DP表
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if str1[i-1] == str2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        
        # 回溯构造超序列
        result = []
        i, j = m, n
        while i > 0 and j > 0:
            if str1[i-1] == str2[j-1]:
                result.append(str1[i-1])
                i -= 1
                j -= 1
            elif dp[i-1][j] > dp[i][j-1]:
                result.append(str1[i-1])
                i -= 1
            else:
                result.append(str2[j-1])
                j -= 1
        
        # 添加剩余字符
        while i > 0:
            result.append(str1[i-1])
            i -= 1
        while j > 0:
            result.append(str2[j-1])
            j -= 1
        
        return ''.join(reversed(result))

public class Solution {
    public string ShortestCommonSupersequence(string str1, string str2) {
        int m = str1.Length, n = str2.Length;
        int[,] dp = new int[m + 1, n + 1];
        
        // 构建LCS的DP表
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (str1[i-1] == str2[j-1]) {
                    dp[i,j] = dp[i-1,j-1] + 1;
                } else {
                    dp[i,j] = Math.Max(dp[i-1,j], dp[i,j-1]);
                }
            }
        }
        
        // 回溯构造超序列
        StringBuilder result = new StringBuilder();
        int x = m, y = n;
        while (x > 0 && y > 0) {
            if (str1[x-1] == str2[y-1]) {
                result.Insert(0, str1[x-1]);
                x--;
                y--;
            } else if (dp[x-1,y] > dp[x,y-1]) {
                result.Insert(0, str1[x-1]);
                x--;
            } else {
                result.Insert(0, str2[y-1]);
                y--;
            }
        }
        
        // 添加剩余字符
        while (x > 0) {
            result.Insert(0, str1[x-1]);
            x--;
        }
        while (y > 0) {
            result.Insert(0, str2[y-1]);
            y--;
        }
        
        return result.ToString();
    }
}

var shortestCommonSupersequence = function(str1, str2) {
    const m = str1.length;
    const n = str2.length;
    
    // Build LCS DP table
    const dp = Array(m + 1).fill().map(() => Array(n + 1).fill(0));
    
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (str1[i - 1] === str2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    
    // Build the supersequence by backtracking
    let result = '';
    let i = m, j = n;
    
    while (i > 0 && j > 0) {
        if (str1[i - 1] === str2[j - 1]) {
            result = str1[i - 1] + result;
            i--;
            j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            result = str1[i - 1] + result;
            i--;
        } else {
            result = str2[j - 1] + result;
            j--;
        }
    }
    
    // Add remaining characters
    while (i > 0) {
        result = str1[i - 1] + result;
        i--;
    }
    
    while (j > 0) {
        result = str2[j - 1] + result;
        j--;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(m×n) - 需要填充大小为(m+1)×(n+1)的DP表，然后回溯构造结果
空间复杂度O(m×n) - 存储DP表的空间，结果字符串的长度最多为m+n

相关题目