2ms java solution beats 100%


  • 0
    R
    int[] text1,text2;
    public boolean isScramble(String s1, String s2) {
        if(s1.length()<=1)return s1.length()==1?s1.charAt(0)==s2.charAt(0):true;
        //compare two int array rather than string
        text1=new int[s1.length()];
        text2=new int[s2.length()];
        int i=0;
        for(char c:s1.toCharArray()){
            text1[i]=c-'a';
            i++;
        }
        i=0;
        for(char c:s2.toCharArray()){
            text2[i]=c-'a';
            i++;
        }
        //check if input is anagram
        int difference=0;
        int[] check=new int[32];
        for(i=0;i<text1.length;i++){
            if(check[text1[i]]++>=0)difference++;
            else difference--;
            if(check[text2[i]]--<=0)difference++;
            else difference--;
        }
        if(difference!=0)return false;
        //only anagram will make this call
        return solve(0,text1.length-1,0,text2.length-1);
    }
    
    public boolean solve(int begin1,int end1,int begin2, int end2){
        //only one char
        if(end1-begin1<=0)return text1[begin1]==text2[begin2];
        boolean ret=false;
        
        //below loop can be commented out, but algorithm will have better performance if below loop is added
        for(int i=0;begin1+i<=end1;i++){
            if(text1[begin1+i]==text2[begin2+i]){
                if(begin1+i==end1)return true;
            }
            else break;
        }
        
        int difference=0;
        int[] check=new int[32];
        //if root level does not rotate, match left part and right part respectively
        for(int i=0;begin1+i<end1;i++){
            if(check[text1[begin1+i]]++>=0)difference++;
            else difference--;
            if(check[text2[begin2+i]]--<=0)difference++;
            else difference--;
            if(difference==0){
                ret=solve(begin1,begin1+i,begin2,begin2+i)&&solve(begin1+i+1,end1,begin2+i+1,end2);
                if(ret)return true;
            }
        }
        
        //root rotate, find each symmetric point (anagram) text1 left match text2 right, text1 right match text2 left
        difference=0;
        check=new int[32];
        for(int i=0;begin1+i<end1;i++){
            if(check[text1[begin1+i]]++>=0)difference++;
            else difference--;
            if(check[text2[end2-i]]--<=0)difference++;
            else difference--;
            if(difference==0){
                ret=solve(begin1,begin1+i,end2-i,end2)&&solve(begin1+i+1,end1,begin2,end2-i-1);
                if(ret)return true;
            }
        }
        
        return false;
    }

Log in to reply
 

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