Interleaving String
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac",
return true.
When s3 = "aadbbbaccc", return
false.
这种题目应该立即反应需要动态规划法，会填表，然后翻译为程序。可以用递归法求解，但是会超时，而且好像都不容易写。
不过这里是三个字符串，应该如何设计这个表是个大问题。
这里用s1和s2作为二维表的两个维的下标，然后徐两个下标相加得到s3的一维下标，进行比较字符。这是本题关键，也是这个表这么难设计，所以本题的难度还是很高的。对没接触过这类题目的人来说，应该是五星级难度的题目了。
bool isInterleave(string s1, string s2, string s3)
{
int n1 = s1.length(), n2 = s2.length(), n3 = s3.length();
if (n1+n2 != n3) return false;
vector<vector<bool> > ta(n1+1, vector<bool>(n2+1));
ta[0][0] = true;
for (int i = 1; i <= n2; i++)
{
if (ta[0][i-1] && s2[i-1] == s3[i-1]) ta[0][i] = true;
else break;
}
for (int i = 1; i <= n1; i++)
{
if (ta[i-1][0] && s1[i-1]==s3[i-1]) ta[i][0] = true;
for (int j = 1; j <= n2; j++)
{
if (ta[i][j-1] && s2[j-1] == s3[i+j-1]) ta[i][j] = true;
else if (ta[i-1][j] && s1[i-1] == s3[i+j-1]) ta[i][j] = true;
}
}
return ta[n1][n2];
}