You are given three strings s1, s2 and s3. Decide whether s3 can be made by mixing s1 and s2.
To make s3, take letters one by one. Each time you may take the next unused letter of s1 or the next unused letter of s2. The letters of each string must stay in their own order. Continue until both strings are fully used. Return true if you can build exactly s3 this way, and false if you cannot.
Examples
Example 1:
Input: s1 = "ab", s2 = "cd", s3 = "acbd"
Output: true
Explanation: Take a from s1, c from s2, b from s1, d from s2.
Example 2:
Input: s1 = "ab", s2 = "cd", s3 = "adbc"
Output: false
Explanation: After taking a, the next letter of s2 is c, not d. Taking d here would break the order of s2.
Example 3:
Input: s1 = "", s2 = "xy", s3 = "xy"
Output: true
Explanation: Only s2 has letters, and they stay in order.