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
andstr2
consist of lowercase English letters.
Problem Analysis:
This problem is similar to solve longest common subsequence(LCS) problem. As the final string is str1 + str2-LCS. We can use dynamic programming to compute the LCS and then get the final string.
Assume dp[i][j] is the longest common substring length with str1 in [0..i-1] and str2 in [0..j-1]. We can get the dp values in two cases: first, when str1[i-1] = str2[j-1], then dp[i][j] = dp[i-1][j-1] + 1, otherwise, dp[i][j] = max(dp[i-1][j], dp[i-1][j]).
Then we can get the final string after delete the LCS characters.
Solution
class Solution {
public:
string shortestCommonSupersequence(string str1, string str2) {
vector<vector<int>> dp(str1.size() + 1, vector<int>(str2.size() + 1));
string res;
for (int i = 1; i <= str1.size(); ++i) {
for (int j = 1; j <= str2.size(); ++j) {
if (str1[i - 1] == str2[j - 1]) dp[i][j] = 1 + dp[i - 1][j - 1];
else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
int i{(int)str1.size()}, j{(int)str2.size()};
while (i > 0 && j > 0) {
if (str1[i - 1] == str2[j - 1]) {
res.push_back(str1[i - 1]);
--i;
--j;
} else {
if (dp[i - 1][j] > dp[i][j - 1]) {
res.push_back(str1[i - 1]);
--i;
} else {
res.push_back(str2[j - 1]);
--j;
}
}
}
while (i > 0) {
res.push_back(str1[i - 1]);
--i;
}
while (j > 0) {
res.push_back(str2[j - 1]);
--j;
}
reverse(begin(res), end(res));
return res;
}
};
Time complexity is O(mn)
Space complexity is O(mn)