Interleaving Strings

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.

Solution: using DP. This question is very similar to "Find all path", you can just imagine, taking string1 is just as going down, and taking string2 is like to going right.

Java语言: InterleavingString

01 public boolean isInterleave(String s1, String s2, String s3) {
02     int m=s1.length();
03     int n=s2.length();
04     int len=s3.length();
05     if(m+n!=len)
06         return false;
07     if(m==0)
08         return s2.equals(s3);
09     if(n==0)
10         return s1.equals(s3);
11     //DP approach, initiate a 2D array to store 
12     //the validity of the interleaving to the current point
13     boolean [][]array=new boolean[m+1][n+1];
14     for(int i=1;i<=m;i++)
15     {
16         if(s1.charAt(i-1)==s3.charAt(i-1))
17         {
18             array[i][0]=true;
19         }
20     }
21     for(int j=1;j<=n;j++)
22     {
23         if(s2.charAt(j-1)==s3.charAt(j-1))
24         {
25             array[0][j]=true;
26         }
27     }
28     for(int i=1;i<=m;i++)
29     {
30         for(int j=1;j<=n;j++)
31         {
32             //take character from s1
33             if(s1.charAt(i-1)==s3.charAt(i+j-1) && array[i-1][j]==true)
34                 array[i][j]=true;
35             //take character from s2    
36             if(s2.charAt(j-1)==s3.charAt(i+j-1) && array[i][j-1]==true)
37                 array[i][j]=true;
38         }
39     }
40     return array[m][n];
41 }