Monday, January 13, 2014




public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1==null||s1.length()==0|| s2==null ||s2.length()==0 ||s3==null||s3.length()==0){
            return false;
        }
        if (s1.length()+s2.length()!=s3.length()){
            return false;
        }
        
        int index1=0;
        int index2=0;
        int index3=0;
        return helper(s1,index1, s2, index2, s3, index3);
    }
    
    private boolean helper 
                     (String s1, int index1, String s2, int index2, String s3, int index3){
       
        if (index1==s1.length() && index2==s2.length() && index3==s3.length()){
            return true;
        }
        else if (index1==s1.length()){
            if (s3.charAt(index3)!=s2.charAt(index2)){
                return false;
            }
            return helper(s1, index1, s2, index2+1, s3, index3+1);
        }
        else if (index2==s2.length()){
            if (s3.charAt(index3)!=s1.charAt(index1)){
                return false;
            }
            
            return helper(s1, index1+1, s2, index2, s3, index3+1);
            
        }
        else{
            
            
            if (s3.charAt(index3)==s2.charAt(index2) && s2.charAt(index2)==s3.charAt(index3)){
                 return helper(s1, index1+1, s2, index2, s3, index3+1) ||
                        helper(s1, index1, s2, index2+1, s3, index3+1);
            }
            else if (s3.charAt(index3)==s1.charAt(index1)){
                return helper(s1, index1+1, s2, index2, s3, index3+1);
            }
            else{
                return helper(s1, index1, s2,index2+1, s3, index3+1);   
            }
            
            
        }
        
    }
}