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 t if you can delete zero or more characters from t and get s without changing the relative order of the remaining characters.
Input
str1: a string
str2: a string
Output
A shortest common supersequence of str1 and str2.
Examples
Example 1
Inputstr1 = "abac", str2 = "cab"
Output"cabac"
Explanation: str1 = "abac" is a subsequence of "cabac" (delete the leading 'c'). str2 = "cab" is a subsequence of "cabac" (delete the trailing "ac"). Length 5 is the minimum possible.
Constraints
0 <= str1.length, str2.length <= 1000
str1 and str2 consist of lowercase English letters.