String C is considered to be an interleaving of strings A and B if it contains all (and only) the characters of both A and of B and their respective order is preserved in C. For example, C = aacabbaa is an interleaving of A = aaba and B = caba (demonstrated as follows: aacabbaa).
Give an algorithm that, given strings A, B, and C, decides whether C is an interleaving of A and B in polynomial time. Prove your answer correct.