1092. Shortest Common Supersequence LeetCode Solution
In this guide, you will get 1092. Shortest Common Supersequence LeetCode Solution with the best time and space complexity. The solution to Shortest Common Supersequence problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Shortest Common Supersequence
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.
1 <= str1.length, str2.length <= 1000
str1 and str2 consist of lowercase English letters.
Complexity Analysis
Time Complexity: O(mn)
Space Complexity: O(mn^2 \cdot |\texttt{string}|)
1092. Shortest Common Supersequence LeetCode Solution in C++
class Solution {
public:
string shortestCommonSupersequence(string str1, string str2) {
string ans;
int i = 0; // str1's index
int j = 0; // str2's index
for (const char c : lcs(str1, str2)) {
// Append the letters that are not part of the LCS.
while (str1[i] != c)
ans += str1[i++];
while (str2[j] != c)
ans += str2[j++];
// Append the letter of the LCS and match it with str1 and str2.
ans += c;
++i;
++j;
}
// Append the remaining letters.
return ans + str1.substr(i) + str2.substr(j);
}
private:
string lcs(const string& a, const string& b) {
const int m = a.length();
const int n = b.length();
// dp[i][j] := the length of LCS(a[0..i), b[0..j))
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 (a[i - 1] == b[j - 1])
dp[i][j] = dp[i - 1][j - 1] + a[i - 1];
else
dp[i][j] = dp[i - 1][j].length() > dp[i][j - 1].length()
? dp[i - 1][j]
: dp[i][j - 1];
return dp[m][n];
}
}; /* code provided by PROGIEZ */
1092. Shortest Common Supersequence LeetCode Solution in Java
class Solution {
public String shortestCommonSupersequence(String str1, String str2) {
StringBuilder sb = new StringBuilder();
int i = 0; // str1's index
int j = 0; // str2's index
for (final char c : lcs(str1, str2).toCharArray()) {
// Append the letters that are not part of the LCS.
while (str1.charAt(i) != c)
sb.append(str1.charAt(i++));
while (str2.charAt(j) != c)
sb.append(str2.charAt(j++));
// Append the letter of the LCS and match it with str1 and str2.
sb.append(c);
++i;
++j;
}
// Append the remaining letters.
return sb.toString() + str1.substring(i) + str2.substring(j);
}
private String lcs(final String a, final String b) {
final int m = a.length();
final int n = b.length();
// dp[i][j] := the length of LCS(a[0..i), b[0..j))
StringBuilder[][] dp = new StringBuilder[m + 1][n + 1];
for (final StringBuilder[] row : dp)
for (int i = 0; i < row.length; ++i)
row[i] = new StringBuilder();
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j)
if (a.charAt(i - 1) == b.charAt(j - 1))
dp[i][j].append(dp[i - 1][j - 1]).append(a.charAt(i - 1));
else
dp[i][j] = dp[i - 1][j].length() > dp[i][j - 1].length() ? dp[i - 1][j] : dp[i][j - 1];
return dp[m][n].toString();
}
} // code provided by PROGIEZ
1092. Shortest Common Supersequence LeetCode Solution in Python
