算法：29.交叉字符串

https://www.lintcode.com/problem/interleaving-string/description

描述

给出三个字符串:s1、s2、s3，判断s3是否由s1和s2交叉构成。

样例

比如 s1 ="aabcc"s2 ="dbbca"

- 当 s3 ="aadbbcbcac"，返回 true.

- 当 s3 ="aadbbbaccc"， 返回 false.

挑战

要求时间复杂度为O(n^2)或者更好

思路

在s3中交替搜索s1，s2的子串，如果能轮番找到子串，并刚好搜索完三个字符串则返回true。关键在于搜索失败时的搜索位置回退。

代码

小结

代码较短，但是耗时稍长，暂时想不到提升的办法。