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 { 2 public boolean isInterleave(String s1, String s2, String s3) { 3 int len1 = s1.length(); 4 int len2 = s2.length(); 5 int len3 = s3.length(); 6 if(len1+len2!=len3) return false; 7 boolean[][] match= new boolean[len1+1][len2+1];//define [][] is the length of the string! [0] means "null" 8 int i =1;//should from 1 9 match[0][0]=true; 10 while(i<=len1 &&s1.charAt(i-1)==s3.charAt(i-1)){ 11 match[i][0]=true; 12 i++; 13 } 14 i=1; 15 while(i<=len2 &&s2.charAt(i-1)==s3.charAt(i-1)){ 16 match[0][i]=true; 17 i++; 18 } 19 for(int m=1;m<=len1;m++){ 20 for(int n=1;n<=len2;n++){ 21 if(s1.charAt(m-1)==s3.charAt(m+n-1)){ 22 match[m][n] |= match[m-1][n]; 23 } 24 if(s2.charAt(n-1)==s3.charAt(m+n-1)){ 25 match[m][n] |= match[m][n-1]; 26 } 27 } 28 29 } 30 return match[len1][len2]; 31 } 32 }