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.
//exceed time in large
public class Solution { public boolean isInterleave(String s1, String s2, String s3) { // Start typing your Java solution below // DO NOT write main() function if(s1.length()+s2.length() != s3.length()){ return false; } return isinterleave(s1, 0,s2,0, s3, 0); } public boolean isinterleave(String s1,int x,String s2, int y,String s3, int z){ if(s1.length() == x && s2.length() == y&& s3.length() == z){ return true; } boolean match = false; if(x < s1.length() && s1.charAt(x) == s3.charAt(z)){ match = isinterleave(s1,x+1,s2,y,s3,z+1); } if(!match &&y < s2.length() && s2.charAt(y) == s3.charAt(z)){//make sure s1 plug in first match = isinterleave(s1,x,s2,y+1,s3,z+1); } return match; } }
pass large judge
public class Solution { public boolean isInterleave(String s1, String s2, String s3) { // Start typing your Java solution below // DO NOT write main() function if(s3.length() != s1.length() + s2.length()) return false; boolean[][] match = new boolean[s1.length()+1][s2.length()+1]; match[0][0]=true; int i=1; while(i<=s1.length() && s1.charAt(i-1)==s3.charAt(i-1)){ match[i][0]=true; i++; } i=1; while(i<=s2.length() && s2.charAt(i-1)==s3.charAt(i-1)){ match[0][i]=true; i++; } for(i=1;i<=s1.length();i++){ for(int j=1;j<=s2.length();j++){ char c = s3.charAt(i+j-1); if(c == s1.charAt(i-1)){ match[i][j] = match[i-1][j]|| match[i][j]; } if(c==s2.charAt(j-1)){ match[i][j] = match[i][j-1]||match[i][j] ; } } } return match[s1.length()][s2.length()]; } }
public class Solution { public boolean isInterleave(String s1, String s2, String s3) { // Start typing your Java solution below // DO NOT write main() function if(s3.length() != s1.length() + s2.length()) return false; boolean[][] match = new boolean[s1.length()+1][s2.length()+1]; match[0][0]=true; int i=1; while(i<=s1.length() && s1.charAt(i-1)==s3.charAt(i-1)){ match[i][0]=true; i++; } i=1; while(i<=s2.length() && s2.charAt(i-1)==s3.charAt(i-1)){ match[0][i]=true; i++; } for(i=1;i<=s1.length();i++){ for(int j=1;j<=s2.length();j++){ char c = s3.charAt(i+j-1); if(c == s1.charAt(i-1) && match[i-1][j]){ match[i][j] = true; } if(c==s2.charAt(j-1) && match[i][j-1]){ match[i][j] = true ; } } } return match[s1.length()][s2.length()]; } }
learned: dp出现在这里 -》相当于s1必须和s1上面的一样，s2必须和s2左边的一样，