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"str1 = "abac" is a subsequence of "cabac" by deleting the first "c", and str2 = "cab" is a subsequence by deleting the last "ac"; this is the shortest such string.Example 2
Input
str1 = "aaaaaaaa", str2 = "aaaaaaaa"Output
"aaaaaaaa"Both input strings are identical, so the shortest string containing both as subsequences is the string itself.
Constraints
- 1 <= str1.length, str2.length <= 1000
- str1 and str2 consist of lowercase English letters.