Is It an Interleaving
Print yes if the third string can be formed by interleaving the first two,
keeping the internal order of each, and no otherwise.
Every character of both sources must be used, so the lengths must add up.
aab axy aaxaby -> yes
aab axy abaaxy -> no
Greedy matching fails because when both sources offer the same next character
there is no local way to choose. In the first example, position 0 of the result is
a, and both aab and axy start with a. Taking the wrong one strands the
rest.
So both must be tried, and the state is how much of each source has been consumed:
``` can(i, j) = is c[0 .. i+j) an interleaving of a[0..i) and b[0..j) ?
can(i, j) = ( i > 0 and a[i-1] == c[i+j-1] and can(i-1, j) ) or ( j > 0 and b[j-1] == c[i+j-1] and can(i, j-1) ) ```
Note there is no third index. The position in c is always i + j, which is the
observation that turns a three-dimensional state into a two-dimensional one, and
it is the main thing to take away.
Check the total length first. If it does not match, the answer is no and no
table is needed, and skipping that check lets the recursion read past the end of
c.