LeetCode 1092. Shortest Common Supersequence Solution in Java, C++, Python & More | Explanation + Code

Description

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.

Solutions

Solution 1

PythonJavaC++GoTypeScript

class Solution: def shortestCommonSupersequence(self, str1: str, str2: str) -> str: m, n = len(str1), len(str2) f = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): if str1[i - 1] == str2[j - 1]: f[i][j] = f[i - 1][j - 1] + 1 else: f[i][j] = max(f[i - 1][j], f[i][j - 1]) ans = [] i, j = m, n while i or j: if i == 0: j -= 1 ans.append(str2[j]) elif j == 0: i -= 1 ans.append(str1[i]) else: if f[i][j] == f[i - 1][j]: i -= 1 ans.append(str1[i]) elif f[i][j] == f[i][j - 1]: j -= 1 ans.append(str2[j]) else: i, j = i - 1, j - 1 ans.append(str1[i]) return ''.join(ans[::-1])(code-box)

class Solution { public String shortestCommonSupersequence(String str1, String str2) { int m = str1.length(), n = str2.length(); int[][] f = new int[m + 1][n + 1]; for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (str1.charAt(i - 1) == str2.charAt(j - 1)) { f[i][j] = f[i - 1][j - 1] + 1; } else { f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]); } } } int i = m, j = n; StringBuilder ans = new StringBuilder(); while (i > 0 || j > 0) { if (i == 0) { ans.append(str2.charAt(--j)); } else if (j == 0) { ans.append(str1.charAt(--i)); } else { if (f[i][j] == f[i - 1][j]) { ans.append(str1.charAt(--i)); } else if (f[i][j] == f[i][j - 1]) { ans.append(str2.charAt(--j)); } else { ans.append(str1.charAt(--i)); --j; } } } return ans.reverse().toString(); } }(code-box)

class Solution { public: string shortestCommonSupersequence(string str1, string str2) { int m = str1.size(), n = str2.size(); vector<vector<int>> f(m + 1, vector<int>(n + 1)); for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (str1[i - 1] == str2[j - 1]) f[i][j] = f[i - 1][j - 1] + 1; else f[i][j] = max(f[i - 1][j], f[i][j - 1]); } } int i = m, j = n; string ans; while (i || j) { if (i == 0) ans += str2[--j]; else if (j == 0) ans += str1[--i]; else { if (f[i][j] == f[i - 1][j]) ans += str1[--i]; else if (f[i][j] == f[i][j - 1]) ans += str2[--j]; else ans += str1[--i], --j; } } reverse(ans.begin(), ans.end()); return ans; } };(code-box)

func shortestCommonSupersequence(str1 string, str2 string) string { m, n := len(str1), len(str2) f := make([][]int, m+1) for i := range f { f[i] = make([]int, n+1) } for i := 1; i <= m; i++ { for j := 1; j <= n; j++ { if str1[i-1] == str2[j-1] { f[i][j] = f[i-1][j-1] + 1 } else { f[i][j] = max(f[i-1][j], f[i][j-1]) } } } ans := []byte{} i, j := m, n for i > 0 || j > 0 { if i == 0 { j-- ans = append(ans, str2[j]) } else if j == 0 { i-- ans = append(ans, str1[i]) } else { if f[i][j] == f[i-1][j] { i-- ans = append(ans, str1[i]) } else if f[i][j] == f[i][j-1] { j-- ans = append(ans, str2[j]) } else { i, j = i-1, j-1 ans = append(ans, str1[i]) } } } for i, j = 0, len(ans)-1; i < j; i, j = i+1, j-1 { ans[i], ans[j] = ans[j], ans[i] } return string(ans) }(code-box)

function shortestCommonSupersequence(str1: string, str2: string): string { const m = str1.length; const n = str2.length; const f = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0)); for (let i = 1; i <= m; ++i) { for (let j = 1; j <= n; ++j) { if (str1[i - 1] == str2[j - 1]) { f[i][j] = f[i - 1][j - 1] + 1; } else { f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]); } } } let ans: string[] = []; let i = m; let j = n; while (i > 0 || j > 0) { if (i === 0) { ans.push(str2[--j]); } else if (j === 0) { ans.push(str1[--i]); } else { if (f[i][j] === f[i - 1][j]) { ans.push(str1[--i]); } else if (f[i][j] === f[i][j - 1]) { ans.push(str2[--j]); } else { ans.push(str1[--i]); --j; } } } return ans.reverse().join(''); }(code-box)