Shortest Common Supersequence
Given two strings str1 and str2, return the shortest string that contains both of them as subsequences.
A string contains another as a subsequence when the second can be obtained by deleting zero or more characters from the first without reordering the rest. Concatenating the two inputs always produces a supersequence; the task is to find the shortest one.
Input & Output
Input
str1 — the first string that must appear as a subsequence
str2 — the second string that must appear as a subsequence
Output
the shortest string containing both str1 and str2 as subsequences
Example
Input
str1 = "abac", str2 = "cab"
Output
"cabac"
Explanation
Deleting the leading c from "cabac" leaves "abac", and deleting the b and the final c leaves "cab". No string of length 4 contains both, and "cabac" is the only string of length 5 that does.
Example
Input
str1 = "abcde", str2 = "ace"
Output
"abcde"
Explanation
"ace" is already a subsequence of "abcde", so nothing has to be added and the longer string is itself the answer.
Constraints
1 <= str1.length, str2.length <= 1000str1andstr2consist of lowercase English letters- Each test case has exactly one shortest common supersequence, so the answer is compared as an exact string