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 {
public boolean isInterleave(String s1, String s2, String s3) {
if( s1.length()+s2.length() != s3.length())
return false;
if( s1.length()+s2.length() != s3.length())
return false;
if( s1.length() == 0)
return s2.equals(s3);
if( s2.length() == 0)
return s1.equals(s3);
System.out.println(s1.length()+" "+s2.length()+" "+s3.length() );
return getResult(s1,s2,s3,0,0,0);
}
public boolean getResult(String s1,String s2,String s3,int i,int j,int k){
if( i == s1.length() && j == s2.length() && k == s3.length())
return true;
else if( i == s1.length() ){
while( j<s2.length() && s2.charAt(j) == s3.charAt(k)){
j++;
k++;
}
if( j == s2.length() )
return true;
else
return false;
}else if( j == s2.length() ){
while( i<s1.length() && s1.charAt(i) == s3.charAt(k)){
i++;
k++;
}
if( i == s1.length() )
return true;
else
return false;
}else if( s1.charAt(i) == s3.charAt(k) && s2.charAt(j) != s3.charAt(k))
return getResult(s1,s2,s3,i+1,j,k+1);
else if( s2.charAt(j) == s3.charAt(k) && s1.charAt(i) != s3.charAt(k))
return getResult(s1,s2,s3,i,j+1,k+1);
else if( s1.charAt(i) == s3.charAt(k) && s2.charAt(j) == s3.charAt(k)){
boolean res = getResult(s1,s2,s3,i+1,j,k+1);
if( res )
return true;
res = getResult(s1,s2,s3,i,j+1,k+1);
return res?true:false;
}else
return false;
}
}
2、所以使用DP算法
这里就类似于一个二维的地图，判断是否能从左上角走到右下角。
示例：s1="aa",s2="ab",s3="aaba"。标1的为可行。最终返回右下角。
0 a b
0 1 1 0
a 1 1 1
a 1 0 1
最后AC，但是并不算太快。
public class Solution { public boolean isInterleave(String s1, String s2, String s3) { if( s1.length()+s2.length() != s3.length()) return false; if( s1.length() == 0) return s2.equals(s3); if( s2.length() == 0) return s1.equals(s3); boolean[][] result = new boolean[s1.length()+1][s2.length()+1]; result[0][0] = true; for( int i = 0;i<=s1.length();i++){ for( int j = 0;j<=s2.length();j++){ if( i == 0 && j == 0) result[i][j] = true; else if( j == 0){ result[i][0] = result[i-1][0] && s1.charAt(i-1) == s3.charAt(i-1); }else if( i == 0){ result[0][j] = result[0][j-1] && s2.charAt(j-1) == s3.charAt(j-1); } else{ if( result[i-1][j] && s1.charAt(i-1) == s3.charAt(i+j-1)) result[i][j] = true; else if( result[i][j-1] && s2.charAt(j-1) == s3.charAt(i+j-1)) result[i][j] = true; } } } return result[s1.length()][s2.length()]; } }
3、可以在空间上稍微简化一下，使用单数组完成。只是稍作改变，就不再贴出来了。
4、第三种方法是将上述两种方法结合一下，可以达到1ms，最快，这里是借鉴了Discuss里面的一个答案。
public class Solution { public boolean isInterleave(String s1, String s2, String s3) { int[][] memo = new int[s1.length() + 1][s2.length() + 1]; return helper(s1, s2, s3, 0, 0, 0, memo); } private boolean helper(String s1, String s2, String s3, int index1, int index2, int index3, int[][] memo) { if(s1.length() + s2.length() != s3.length()) return false; if(s1.length() == index1 && s2.length() == index2 && s3.length() == index3 ) return true; boolean s1flag = false; boolean s2flag = false; if(index1 < s1.length() && s1.charAt(index1) == s3.charAt(index3)) { if(memo[index1+1][index2] == 1) { s1flag = true; } else if(memo[index1][index2] == 0){ s1flag = helper(s1, s2, s3, index1+1, index2, index3+1, memo); memo[index1+1][index2] = s1flag ? 1 : -1; } } if(index2 < s2.length() && s2.charAt(index2) == s3.charAt(index3)) { if(memo[index1][index2+1] == 1) { s2flag = true; } else if(memo[index1][index2] == 0){ s2flag = helper(s1, s2, s3, index1, index2 + 1, index3 + 1, memo); memo[index1][index2+1] = s1flag ? 1 : -1; } } return s1flag || s2flag; } }