题目
题意：
给你三个字符串s1，s2，s3 问你s3是否由s1和s2互相交叉组成。也就是说s3中的某个子序列是s1，剩下的字符串组成s2。
第一眼感觉是最长公共子序列，一开始的想法是先把s3和s1求最长公共子序列,然后从s3的部分中把s1抠出来，在再和s2求最长公共子序列。
但是这种做法很麻烦，而且是错误的。
正确的思路和最长公共子序列有点相似。
dp[i][j][k] = 1 表示从0-i 的s3区间是由 0-j的s1区间和0-k的s2区间组合而来的。
状态转移方程也很简单。
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int dp[s3.size()+1][s1.size()+1][s2.size()+1];
memset(dp,0,sizeof(dp));
dp[0][0][0]=1;
for(int i=1;i<=s3.size();i++)
{
for(int j=0;j<=s1.size();j++)
{
for(int k=0;k<=s2.size();k++)
{
if(j!=0 && s3[i-1]==s1[j-1]) {
if (dp[i-1][j-1][k]==1)
dp[i][j][k] = 1;
}
if(k!=0 && s3[i-1]==s2[k-1])
{
if(dp[i-1][j][k-1]==1)
dp[i][j][k]=1;
}
}
}
}
if(dp[s3.size()][s1.size()][s2.size()]==1)
return true;
else
return false;
}
}; 复制