For this question, we give you 3 strings and we ask if it is possible to make the 3rd string by merging the 2 other strings. What we mean by merging is that we can cut up both strings into a series of substrings that can be combined to form a 3rd string. The relative order in which characters appear in the first 2 strings must be maintained. Furthermore, you cannot take parts of the first 2 strings to make the 3rd string, all characters must be used when merging.
Input
s1: First string
s2: Second string
s3: Target string that the other 2 strings must be combined to make
Output
Whether or not the 3rd string can be made
Examples
Example 1
Input
s1 = abe
s2 = cdf
s3 = abcdef
Output: true
Explanation
We can make abcdef by doing ab + cd + e + f = abcdef
Example 2
Input
s1 = abe
s2 = cdf
s3 = abcd
Output: false
Explanation
We cannot use parts of the first 2 strings as stated in the problem description so therefore this is not possible.
Constraints
1 <= s1.length, s2.length, s3.length <= 500