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} + ...$

...