Interleaving Strings

Statement

Given strings s1, s2, and s3, find whether an interleaving of s1 and s2 forms s3.

An interleaving of two strings a and b is a configuration where a and b splits into $n$ and $m$ substrings, respectively, such that:

• a $= a_{1}$ + $a_{2}$ + … + $a_{n}$
• b $= b_{1}$ + $b_{2}$ + … + $b_{m}$
• $\left | n - m \right | \leqslant 1$
• The interleaving can follow either of the following two formats:
  • $a_{1} + b_{1} + a_{2} + b_{2} + a_{3} + b_{3} + ...$
  • $b_{1} + a_{1} + b_{2} + a_{2} + b_{3} + a_{3} + ...$
• $a_{x}$ can be a consecutive sequence of characters in string s1.
• $b_{x}$ can be a consecutive sequence of characters in string s2.

Note: $a + b$ is the concatenation of the strings $a$ and $b$.

Let’s say we have two strings, “abc” and “xyz”. We may interleave them in multiple ways. We may alternately pick one character from each string until we have used up all the characters, giving us “axbycz” and “xaybzc”. Or, we may try to pick two characters at a time from each string, giving us “abxycz” and “xyabzc”. If we pick three characters at a time, we get “abcxyz” and “xyzabc”. Another class of variations is to pick a variable number of characters from each string, which leads to many more possibilities, such as “abxcyz”, “xayzbc”, and so on. However, “bxaycz” is not a valid interleaving, as the order of the characters taken from the first string is not preserved, since “b” appears here before “a”. Similarly, “acxybz” is not a valid interleaving.

Constraints:

• $0 \leq$ s1.length, s2.length $\leq 1500$
• $0 \leq$ s3.length $\leq 3000$
• s1, s2, and s3 consist of lowercase English letters.

Examples