Picture two decks of letter cards, s1 and s2, each in a fixed order. You interleave them by repeatedly taking the top card of either deck, as you choose, and laying it at the end of a new row until both decks are used up. The row keeps each deck's own order, but the two decks' cards can be mixed in any pattern.
Return true if the string s3 can come out of interleaving s1 and s2 this way, using every letter of both exactly once, and false otherwise.
Take r from s1, b from s2, e from s1, l from s2, d from s1, and finally u and e from s2.
Both decks start with a, and the choice matters. Taking the first a from s1 leaves b and a on top, and neither matches the c that comes next. Take a and c from s2 first, then a and b from s1.
s3 has exactly the right letters, yet every way gets stuck. If the first a comes from s1, the b must come from s1 too, and then a c is needed while s2 still shows its a. If the first a comes from s2, a b is needed next, but the tops show a and c.
Constraints
0 <= s1.length, s2.length <= 1000 <= s3.length <= 200s1, s2 and s3 are made of lowercase English letters only.If the lengths don't add up, the answer is false. Otherwise, after using the first i letters of s1 and the first j of s2, you have built the first i + j letters of s3, and the next letter must come from s1[i] or s2[j]. Trying both every time repeats work, because the same (i, j) can be reached in many ways.
true