原文链接: https://leetcode-cn.com/problems/shortest-common-supersequence

英文原文

Given two strings str1 and str2, return the shortest string that has both str1 and str2 as subsequences. If there are multiple valid strings, return any of them.

A string s is a subsequence of string t if deleting some number of characters from t (possibly 0) results in the string s.

 

Example 1:

Input: str1 = "abac", str2 = "cab"
Output: "cabac"
Explanation: 
str1 = "abac" is a subsequence of "cabac" because we can delete the first "c".
str2 = "cab" is a subsequence of "cabac" because we can delete the last "ac".
The answer provided is the shortest such string that satisfies these properties.

Example 2:

Input: str1 = "aaaaaaaa", str2 = "aaaaaaaa"
Output: "aaaaaaaa"

 

Constraints:

• 1 <= str1.length, str2.length <= 1000
• str1 and str2 consist of lowercase English letters.

中文题目

给出两个字符串 str1 和 str2，返回同时以 str1 和 str2 作为子序列的最短字符串。如果答案不止一个，则可以返回满足条件的任意一个答案。

（如果从字符串 T 中删除一些字符（也可能不删除，并且选出的这些字符可以位于 T 中的 任意位置），可以得到字符串 S，那么 S 就是 T 的子序列）

 

示例：

输入：str1 = "abac", str2 = "cab"
输出："cabac"
解释：
str1 = "abac" 是 "cabac" 的一个子串，因为我们可以删去 "cabac" 的第一个 "c"得到 "abac"。 
str2 = "cab" 是 "cabac" 的一个子串，因为我们可以删去 "cabac" 末尾的 "ac" 得到 "cab"。
最终我们给出的答案是满足上述属性的最短字符串。

 

提示：

1. 1 <= str1.length, str2.length <= 1000
2. str1 和 str2 都由小写英文字母组成。

通过代码

高赞题解

比较容易想到我们要找的目的字符串由三部分组成：两个字符串的最长公共子序列LCS+第一个字符串除去LCS之后的序列+第二个字符串除去LCS之后的序列。
求LCS是经典的动态规划题目，所以此题相对的难点在于由LCS去构建目的字符串。
同一个字符串中的字符的相对顺序不可改变，所以我们可以用字符串与LCS比较来确定字符的相对位置。

class Solution {
public:
    string shortestCommonSupersequence(string str1, string str2) {
        int n=str1.size(),m=str2.size();
        //求LCS
        vector<vector<string>> dp(n+1,vector<string>(m+1));
        for(int i=1;i<=n;++i)
            for(int j=1;j<=m;++j)
            {
                if(str1[i-1]==str2[j-1])
                    dp[i][j]=dp[i-1][j-1]+str1[i-1];
                else
                    dp[i][j]=(dp[i-1][j].size()>dp[i][j-1].size()?dp[i-1][j]:dp[i][j-1]);
            }
        //构建目的字符串
        string ans,lcs=dp[n][m];
        int i=0,j=0;
        //按照同一个字符串内的字符相对于LCS的顺序构建目的字符串
        for(char ch:lcs)
        {
            //不同字符串的字符相对顺序无关，所以先遍历str1和先遍历str2都可以
            while(i<n&&str1[i]!=ch)
                ans+=str1[i++];
            while(j<m&&str2[j]!=ch)
                ans+=str2[j++];
            ans+=ch,++i,++j;
        }
        //加上每个字符串在LCS之后的字符
        return ans+str1.substr(i)+str2.substr(j);
    }
};

这种做法比较好理解，但时间效率并不高。

统计信息

通过次数	提交次数	AC比率
2785	5676	49.1%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言