My simple java solution


  • -2
    X
    public class Solution {
       
        private Map<String, Boolean> map = new HashMap<String, Boolean>();
        
        public boolean isScramble(String s1, String s2) {
    
            if(map.containsKey(s1+s2)) return map.get(s1+s2);
            if(s1.length() != s2.length()){
                return false;
            }
            if(s1.length() == 1 && s2.length() == 1){
                map.put(s1+s2,s1.equals(s2));
                return s1.equals(s2);
            }
    
            int n = s1.length();
            for(int i = 1; i < n; i++){
                String s1_sub1 = s1.substring(0, i);//i
                
                String s2_sub1 = s2.substring(0, i);   //i
                String s2_sub2 = s2.substring(n - i, n);//i
                
                String s1_sub2 = s1.substring(i, n);//n - i
                
                String s2_sub11 = s2.substring(i, n); // n - i
                String s2_sub22 = s2.substring(0, n - i); // n - i;
                if(isScramble(s1_sub1, s2_sub1) && isScramble(s1_sub2, s2_sub11)){
                    //contain(s1, s2);
                    map.put(s1+s2,true);
                    return true;
                }
                if(isScramble(s1_sub1, s2_sub2) && isScramble(s1_sub2, s2_sub22)){
                    //contain(s1, s2);
                    map.put(s1+s2,true);
                    return true;
                }
                
            }
            map.put(s1+s2,false);
            return false;
        }
        
    
        
    }

Log in to reply
 

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