beats 88% ! java concise solution


  • 1
    T

    public class Solution {

    boolean[][] visited;
    
    public boolean isInterleave(String s1, String s2, String s3) {
        if(s1==null||s1.length()==0) return s2.equals(s3);
        if(s2==null||s2.length()==0) return s1.equals(s3);
        if(s3==null||s3.length()==0) return (s1==null&&s2==null)||(s1.length()==0&&s2.length()==0);
        if(s1.length()+s2.length()!=s3.length()) return false;
        
        visited=new boolean[s1.length()+1][s2.length()+1];
        
        return rec(s1,0,s2,0,s3,0);
    }
    
    public boolean rec(String s1,int i1,String s2,int i2,String s3,int i3){
        //exit
        if(visited[i1][i2])
            return false;
        
        if(i3==s3.length())
            return i1==s1.length()&&i2==s2.length();
        else if(i1==s1.length()){
            return s3.substring(i3).equals(s2.substring(i2));
        }
        else if(i2==s2.length()){
            return s3.substring(i3).equals(s1.substring(i1));
        }
        
        
        boolean res;
        if(s1.charAt(i1)==s3.charAt(i3) && s2.charAt(i2)==s3.charAt(i3)){
            res=rec(s1,1+i1,s2,i2,s3,1+i3)||rec(s1,i1,s2,1+i2,s3,1+i3);
        }
        else if(s1.charAt(i1)==s3.charAt(i3)){
            res=rec(s1,1+i1,s2,i2,s3,1+i3);
        }
        else if(s2.charAt(i2)==s3.charAt(i3)){
            res=rec(s1,i1,s2,1+i2,s3,1+i3);
        }
        else 
            res=false;
        
        visited[i1][i2]=true;
        return res;
        
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.