这个问题，前面思考过，当时就是用搜索的方法，此处又遇到一次，发现自己理解的太浅了
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.搜索的方法(超时)
1 public class Solution { 2 public boolean isInterleave(String s1, String s2, String s3) { 3 return isInter(s1,s2,s3,0,0,0); 4 5 6 } 7 public boolean isInter(String s1,String s2,String s3,int r1,int r2, int r3) 8 { 9 if(r3==s3.length()) return true; 10 boolean ans=false; 11 12 if(r1<s1.length()&&s1.charAt(r1)==s3.charAt(r3)) 13 { 14 ans=isInter(s1,s2,s3,r1+1,r2,r3+1); 15 16 17 18 } 19 if(ans) return true; 20 21 if(r2<s2.length()&&s2.charAt(r2)==s3.charAt(r3)) 22 { 23 ans=isInter(s1,s2,s3,r1,r2+1,r3+1); 24 return ans; 25 26 27 28 } 29 30 return false; 31 32 33 } 34 }
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]
1 public class Solution { 2 public boolean isInterleave(String s1, String s2, String s3) { 3 char c1[]=s1.toCharArray(); 4 5 char c2[]=s2.toCharArray(); 6 char c3[]=s3.toCharArray(); 7 int len1=s1.length(); 8 int len2=s2.length(); 9 int len3=s3.length(); 10 if(len1+len2!=len3) return false; 11 if(len1==0) return s2.equals(s3); 12 if(len2==0) return s1.equals(s3); 13 14 boolean dp[][]=new boolean[s1.length()+1][s2.length()+1]; 15 dp[0][0]=true; 16 for(int i=1;i<=len1;i++) 17 { 18 19 dp[i][0]=dp[i-1][0]&&c1[i-1]==c3[i-1]; 20 21 } 22 for(int j=1;j<=len2;j++) 23 { 24 25 dp[0][j]=dp[0][j-1]&&c2[j-1]==c3[j-1]; 26 } 27 28 29 30 for(int i=1;i<=len1;i++) 31 { 32 33 for(int j=1;j<=len2;j++) 34 { 35 36 37 dp[i][j]=dp[i-1][j]&&(c1[i-1]==c3[i+j-1]); 38 if(dp[i][j]) continue; 39 dp[i][j]=dp[i][j-1]&&(c2[j-1]==c3[i+j-1]); 40 41 } 42 43 44 45 } 46 47 48 return dp[len1][len2]; 49 50 51 } 52 53 }