400. Shortest common supersequence
Given two strings str1 and str2, find the shortest common supersequence.
The shortest common supersequence is the shortest string that contains both str1 and str2 as subsequences.
Note: The problem may have multiple valid answers. Since the return type is a string, the judge will output 1 if your returned string is a valid shortest common supersequence and 0 otherwise.
Example 1:
Input: str1 = "mno", str2 = "nop"
Output: "mnop"
Explanation: The shortest common supersequence is "mnop". It contains "mno" as the first three characters and "nop" as the last three characters, thus including both strings as subsequences.
Example 2:
Input: str1 = "dynamic", str2 = "program"
Output: "dynprogramic"
Explanation: The shortest common supersequence is "dynprogramic". It includes all characters from both "dynamic" and "program", with minimal overlap. For example, "dynamic" appears as "dyn...amic" and "program" appears as "...program..." within "dynprogramic".
Now Your Turn!
Pick the correct output for the given inputInput: str1 = "apple", str2 = "orange"
Still unsure what the problem is asking ?
Let’s go through a few more examples, step by step, to make it clearer.
Constraints:
- 1 <= str1.length, str2.length <= 1000
- str1 and str2 consist of lowercase English letters.