## Algorithm

Problem Name: 1092. 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 <= 1000`
• `str1` and `str2` consist 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]
}
``````
Copy The Code &

Input

cmd
str1 = "abac", str2 = "cab"

Output

cmd
"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:]
``````
Copy The Code &

Input

cmd
str1 = "abac", str2 = "cab"

Output

cmd
"cabac"