Given two strings str1 and str2, return the shortest string that has both str1 and str2 as subsequences.  If multiple answers exist, you may return any of them.

(A string S is a subsequence of string T if deleting some number of characters from T (possibly 0, and the characters are chosen anywhere from T) 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.

Note:

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

这道题给了两个字符串 str1 和 str2，让找出包含这两个字符串为子序列的最短字符串，即最短公共超序列。分析例子可以发现，之所以最终返回的字符串长度为5，是因为给定的两个字符串中都含有子序列 ab，这样的话就可以缩小总的长度了。看来 str1 和 str2 的最长公共子序列越长，说明可重叠的部分越长，则最终返回的公共超序列的长度越短，那么这道题就转为了求最长公共子序列 Longest Common Subsequence 的问题，也就是之后的这道 Longest Common Subsequence，还好博主提前做过。是使用动态规划 Dynamic Programming 来做的，不过略有不同的是，这里需要知道 LCS 具体是什么，而不仅仅是长度。所以这里的 DP 数组就要定义为二维字符串数组，但是状态转移方程还是一样的，若二者对应位置的字符相同，表示当前的 LCS 又增加了一位，所以可以用 dp[i-1][j-1] + str1[i-1] 来更新 dp[i][j]。否则若对应位置的字符不相同，由于是子序列，还可以错位比较，可以分别从 str1 或者 str2 去掉一个当前字符，那么其 dp 值就是 dp[i-1][j] 和 dp[i][j-1]，取二者中的长度较大值来更新 dp[i][j] 即可，最终的结果保存在了 dp[m][n] 中。知道了 LCS 的字符串，就要来生成最短公共超序列了，需要使用个双指针，分别指向 str1 和 str2 的开头，然后遍历 LCS 中所有的字符，对于每个遍历到的字符，用 while 循环将 str1 中从i位置到当前字符之间的所有字符加到 res 中，同理，用 while 循环将 str2 中从j位置到当前字符之间的所有字符加到 res 中。然后 res 加上当前字符，并且i和j再分别自增1。遍历完 LCS 之后，有可能i和j还没有到 str1 和 str2 的末尾，所以需要将剩余的子串再分别加到 res 中即可，参见代码如下：

class Solution {
public:
    string shortestCommonSupersequence(string str1, string str2) {
        string res;
        int m = str1.size(), n = str2.size();
        vector<vector<string>> dp(m + 1, vector<string>(n + 1));
        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] + 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];
                }
            }
        }
        int i = 0, j = 0;
        for (char c : dp[m][n]) {
            while (i < m && str1[i] != c) res += str1[i++];
            while (j < n && str2[j] != c) res += str2[j++];
            res += c;
            ++i; ++j;
        }
        return res + str1.substr(i) + str2.substr(j);
    }
};

Github 同步地址:

#1092

类似题目：

Longest Common Subsequence

参考资料：

https://leetcode.com/problems/shortest-common-supersequence/

https://leetcode.com/problems/shortest-common-supersequence/discuss/312710/C%2B%2BPython-Find-the-LCS

https://leetcode.com/problems/shortest-common-supersequence/discuss/312702/Java-DP-Solution(Similiar-to-LCS)

LeetCode All in One 题目讲解汇总(持续更新中...)