lintCode(29) Interleaving String

Given three strings: s1, s2, s3, determine whether s3 is formed by the interleaving of s1 and s2.

Have you met this question in a real interview? 

Yes

Example

For s1 = "aabcc", s2 = "dbbca"

• When s3 = "aadbbcbcac", return true.
• When s3 = "aadbbbaccc", return false.

Challenge

O(n2) time or better

dp, f[i][j]为前i个s1和前j个s2能否组成前i+j个s3.。。

转移方程比较简单， 见代码