给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。
示例 1:
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" 输出: true
示例 2:
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc" 输出: false
解答：对于此题目可以用递归来进行处理。首先对s1、s2联合字符串排序，再与排序后的s3比较，如果存在不相同的字符，那么直接返回false。
递归函数很简单，就是逐次比较。缺点：运算时间长，对于长字符串出现了TLE（Time Limit Exceeded）问题。
bool isInterleaveHelper(string s1,string s2, string s3) { if(s1.empty()) return s2==s3?true:false; if(s2.empty()) return s1==s3?true:false; for(int m=0;m<(int)s3.size();m++) { if(s1[0] == s3[m] && isInterleaveHelper(s1.substr(1),s2,s3.substr(1))) return true; if(s2[0] == s3[m] && isInterleaveHelper(s1,s2.substr(1),s3.substr(1))) return true; return false; } return false; } //97 bool isInterleave(string s1, string s2, string s3) { string temp1 = s1+s2; string temp2 = s3; sort(temp1.begin(),temp1.end()); sort(temp2.begin(),temp2.end()); if(temp1!=temp2) return false; return isInterleaveHelper(s1,s2,s3); }//97
优化递归算法：
s3比较的对象为s2和s1，所以可以构建一个二维的数组用于记录当前的查询位置。在这里首先从得到二维数组边缘的信息。然后从尾到头依次比较在位置k处的s3是否符合配对，符合则记为true。
最后可以得到最终结果。这种算法内存和耗时都不是最优，还有改进的空间。
bool isInterleave(string s1, string s2, string s3) { if(s1.empty()) return s2==s3?true:false; if(s2.empty()) return s1==s3?true:false; string temp1 = s1+s2; string temp2 = s3; sort(temp1.begin(),temp1.end()); sort(temp2.begin(),temp2.end()); if(temp1!=temp2) return false; int m = s1.size(); int n = s2.size(); vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false)); for(int i=0;i<m;i++) dp[i][n] = (s1.substr(i) == s3.substr(n + i));//最右侧列，自下向上 for(int j=0;j<n;j++) dp[m][j] = (s2.substr(j) == s3.substr(m + j));//最底层行，自右向左 dp[m][n] = true; for(int i = m - 1 ; i >= 0; --i) for(int j = n - 1; j >= 0; --j) { if(s3[i + j] == s1[i]) dp[i][j] = dp[i][j] || dp[i+1][j];//列 向上 if(s3[i + j] == s2[j]) dp[i][j] = dp[i][j] || dp[i][j+1];//行 向左 } return dp[0][0]; }//97