# 1092. Shortest Common Supersequence

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.

``````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

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 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation