Leetcode 1092: Shortest Common Supersequence

dume0011
2 min readMay 14, 2024

--

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.

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)

--

--