原题网址：https://www.lintcode.com/zh-cn/problem/interleaving-string/#
给出三个字符串:s1、s2、s3，判断s3是否由s1和s2交叉构成。
您在真实的面试中是否遇到过这个题？
Yes
样例
比如 s1 = "aabcc" s2 = "dbbca"
- 当 s3 = "aadbbcbcac"，返回 true.
- 当 s3 = "aadbbbaccc"， 返回 false.
挑战
要求时间复杂度为O(n^2)或者更好
标签
思路：动态规划。
【只要是遇到字符串的子序列或是匹配问题直接就上动态规划Dynamic Programming。】
dp[i][j]表示s3前i+j个字符能否由s1的前i个和s2的前j个组成，那么子问题就是dp[i-1][j]或者dp[i][j-1]，只有子问题成立（true）并且s3第i+j个字符与s1第i个字符相同或者与s2第j个字符相同，该问题才会成立。
本质是求dp，dp二维数组出来了，直接返回dp[s1.size()][s2.size()]即可。
dp[0][0]=true，因为s3前0个字符一定可以由s1前0个字符、s2前0个字符交叉构成；
dp[i][j]：
若dp[i-1][j]为true，即是说s3前i-1+j个字符由s1前i-1个字符、s2前j个字符交叉组成，如果s3第i+j个字符s3[i+j-1]等于s1第i个字符s1【i-1】,则dp[i][j]必为true。
若dp[i][j-1]为true，s3前i-1+j个字符由s1前i个字符、s2前j-1个字符交叉组成，如果s3第i+j个字符s3[i+j-1]等于s2第j个字符s2【j-1】，则dp[i][j]必为true。
即dp[i][j] = dp[i-1][j] && (s3[i+j-1] == s1[i-1]) || dp[i][j-1] && ( s3[i+j-1] == s2[j-1] ) .
考虑边界情况求dp[i][j]时，即dp的第一行和第一列，i或者j等于0，i-1、j-1小于0，字符串下标越界，所以要单独处理。这两种情况相当于单独判断s3的前n位是否由s1前n位或者s2前n位构成，两个for循环即可，本质上与求dp[i][j]没什么区别，只不过不用考虑 ||运算 另一半的情况，因为另一半相当于不存在。
AC代码：
class Solution {
public:
/**
* @param s1: A string
* @param s2: A string
* @param s3: A string
* @return: Determine whether s3 is formed by interleaving of s1 and s2
*/
bool isInterleave(string &s1, string &s2, string &s3) {
// write your code here
int size1=s1.size();
int size3=s3.size();
int size2=s2.size();
if ((size1+size2)!=size3)
{
return false;
}
if (size1==0)
{
return s2==s3;
}
if (size2==0)
{
return s1==s3;
}
vector<vector<bool>> dp(size1+1,vector<bool>(size2+1,false));//动态规划数组;
dp[0][0]=true;
for (int i=1;i<=size1;i++)
{
dp[i][0]=dp[i-1][0]&&(s1[i-1]==s3[i-1]);//dp数组的索引比s1、s2、s3大1,所以s1、s2、s3的当前位为i-1;
}
for (int j=1;j<=size2;j++)
{
dp[0][j]=dp[0][j-1]&&(s2[j-1]==s3[j-1]);
}
for (int i=1;i<=size1;i++)
{
for (int j=1;j<=size2;j++)
{
dp[i][j]=(dp[i-1][j]&&s3[i-1+j]==s1[i-1]||dp[i][j-1]&&s3[j-1+i]==s2[j-1]);
}
}
return dp[size1][size2];
}
};