Problem
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.
Solution
/**
* @param {string} str1
* @param {string} str2
* @return {string}
*/
var shortestCommonSupersequence = function(str1, str2) {
var dp = Array(str1.length).fill(0).map(() => Array(str2.length));
var helper = function(i, j) {
if (i === str1.length) return str2.slice(j);
if (j === str2.length) return str1.slice(i);
if (dp[i][j] !== undefined) return dp[i][j];
var res = '';
if (str1[i] === str2[j]) {
res = str1[i] + helper(i + 1, j + 1);
} else {
var s1 = str1[i] + helper(i + 1, j);
var s2 = str2[j] + helper(i, j + 1);
res = s1.length < s2.length ? s1 : s2;
}
dp[i][j] = res;
return res;
};
return helper(0, 0);
};
Explain:
nope.
Complexity:
- Time complexity : O(n * m).
- Space complexity : O(n * m).