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 <= str1.length, str2.length <= 1000str1andstr2consist 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 同步地址:
https://github.com/grandyang/leetcode/issues/1092
类似题目：
参考资料：
https://leetcode.com/problems/shortest-common-supersequence/
LeetCode All in One 题目讲解汇总(持续更新中…)
转载请注明来源于 Grandyang 的博客 (grandyang.com)，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 grandyang@qq.com
