lecode Interleaving String

这个问题，前面思考过，当时就是用搜索的方法，此处又遇到一次，发现自己理解的太浅了

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 }

View Code

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 }

View Code