Algorithm
Problem Name: 1092. Shortest Common Supersequence
Problem Link: https://leetcode.com/problems/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.
Example 2:
Input: str1 = "aaaaaaaa", str2 = "aaaaaaaa" Output: "aaaaaaaa"
Constraints:
1 <= str1.length, str2.length <= 1000str1andstr2consist of lowercase English letters.
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const shortestCommonSupersequence = function(str1, str2) {
const len1 = str1.length
const len2 = str2.length
const mat = Array.from({ length: len1 + 1 }, () =>
new Array(len2 + 1).fill(0)
)
for (let i = 0; i < = len1; i++) {
for (let j = 0; j < = len2; j++) {
if (i == 0) {
mat[i][j] = str2.slice(0, j)
continue
}
if (j == 0) {
mat[i][j] = str1.slice(0, i)
continue
}
mat[i][j] = mat[i - 1][j] + str1[i - 1]
let cand1 = mat[i][j - 1] + str2[j - 1]
if (cand1.length < mat[i][j].length) mat[i][j] = cand1
if (str1[i - 1] === str2[j - 1]) {
let cand2 = mat[i - 1][j - 1] + str1[i - 1]
if (cand2.length < mat[i][j].length) mat[i][j] = cand2
}
}
}
return mat[len1][len2]
}
Input
str1 = "abac", str2 = "cab"
Output
"cabac"
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
def compute_lcs(s, t):
m, n = len(s), len(t)
dp = [[""] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if s[i - 1] != t[j - 1]:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], key=len)
else:
dp[i][j] = dp[i - 1][j - 1] + s[i - 1]
return dp[-1][-1]
cs = compute_lcs(str1, str2)
ans = []
i, j = 0, 0
m, n = len(str1), len(str2)
for ch in cs:
while i < m and str1[i] != ch:
ans.append(str1[i])
i += 1
while j < n and str2[j] != ch:
ans.append(str2[j])
j += 1
ans.append(ch)
i += 1
j += 1
return ''.join(ans) + str1[i:] + str2[j:]
Input
str1 = "abac", str2 = "cab"
Output
"cabac"