这个问题，前面思考过，当时就是用搜索的方法，此处又遇到一次，发现自己理解的太浅了
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.
1.搜索的方法(超时)
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
return isInter(s1,s2,s3,0,0,0);
}
public boolean isInter(String s1,String s2,String s3,int r1,int r2, int r3)
{
if(r3==s3.length()) return true;
boolean ans=false;
if(r1<s1.length()&&s1.charAt(r1)==s3.charAt(r3))
{
ans=isInter(s1,s2,s3,r1+1,r2,r3+1);
}
if(ans) return true;
if(r2<s2.length()&&s2.charAt(r2)==s3.charAt(r3))
{
ans=isInter(s1,s2,s3,r1,r2+1,r3+1);
return ans;
}
return false;
}
}
dp[i][j]表示s1前i 和s2前j个是否能组成s3的前i+j+1个, false 不能 true 能
dp[s1.len-1][s2.len-1] 就是我们的答案
dp[i][j]=dp[i-1][j]&&s1[i]==s3[i+j+1]|| dp[i][j-1]&&s1[j]==s3[i+j+1]
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
char c1[]=s1.toCharArray();
char c2[]=s2.toCharArray();
char c3[]=s3.toCharArray();
int len1=s1.length();
int len2=s2.length();
int len3=s3.length();
if(len1+len2!=len3) return false;
if(len1==0) return s2.equals(s3);
if(len2==0) return s1.equals(s3);
boolean dp[][]=new boolean[s1.length()+1][s2.length()+1];
dp[0][0]=true;
for(int i=1;i<=len1;i++)
{
dp[i][0]=dp[i-1][0]&&c1[i-1]==c3[i-1];
}
for(int j=1;j<=len2;j++)
{
dp[0][j]=dp[0][j-1]&&c2[j-1]==c3[j-1];
}
for(int i=1;i<=len1;i++)
{
for(int j=1;j<=len2;j++)
{
dp[i][j]=dp[i-1][j]&&(c1[i-1]==c3[i+j-1]);
if(dp[i][j]) continue;
dp[i][j]=dp[i][j-1]&&(c2[j-1]==c3[i+j-1]);
}
}
return dp[len1][len2];
}
}