A shuffle of two strings X and Y is formed by interspersing the characters into a new string, keeping the characters of X and Y in the same order. For example, the string BANANA ANANAS is a shue of the strings BANANA and ANANAS in several different ways.

BANANAANANAS BANANAANANAS BANANANANA

Similarly, the strings PRODGYRNAMAMMIINCG and DYPRONGARMAMMICING are both shuffles of DYNAMIC and PROGRAMMING:

PROGRAMMING PROGRAMMING

Describe and analyze an efficient algorithm to determine, given throe strings A1 [1...m], B [1...n] and C[1...m+n], whether C is a shuffle of A and B.