97. Interleaving String
Your function receives three strings s1, s2, and s3, and returns true if s3 can be produced by weaving s1 and s2 together, and false otherwise.
A weave splits s1 and s2 into chunks and lays the chunks down alternately — every character of both source strings is used exactly once, and within each source string the characters must keep their original left-to-right order. The chunks may alternate any number of times (and either string may contribute several characters in a row).
In other words: reading s3 left to right, each character must be crossed off the front of what remains of s1 or the front of what remains of s2, and by the end both must be fully consumed.
Careful: taking a matching character greedily from whichever string offers it first does not work — sometimes you must take the 'other' copy of a repeated letter.
Example 1:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Explanation: Take "aa" from s1, "dbb" from s2, "c" from s1, "bc" from s2, "c" from s1, "a" from s2 — that spells aadbbcbcac.
Example 2:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false
Explanation: After matching "aadbb", the next character of s3 is 'b', but the remaining fronts are "cc" (from s1) and "ca" (from s2) — no weave can continue.
Constraints:
- 0 ≤ s1.length, s2.length ≤ 100
- 0 ≤ s3.length ≤ 200
- s1, s2 and s3 consist of lowercase English letters only.
Hints:
First check the lengths: if |s1| + |s2| ≠ |s3|, no weave exists. After that, describe a partial weave by just two numbers — how many characters of s1 and of s2 have been consumed.
Let ok(i, j) mean: the suffix of s3 starting at i + j can be woven from s1[i:] and s2[j:]. Each state has at most two moves (take from s1 or from s2), and there are only (|s1|+1)·(|s2|+1) states — memoize them or fill a table bottom-up.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Expected output: true