Easy Readable Java Solution with Pruning


  • 1
    A
    public class Solution {
        public boolean isScramble(String s1, String s2) {
            if(s1.equals("")) return false;
            if(s1.equals(s2)) return true;
            if(!containsSameChars(s1, s2)) return false;
            
            int l = s1.length();
            
            for(int i = 1; i < l; ++i) {
                String t1 = s1.substring(0, i);
                String t2 = s1.substring(i, l);
                
                // check from the head.
                String check = s2.substring(0, i);
                String rest = s2.substring(i, l);
                if(containsSameChars(t1, check)) {
                    if(isScramble(t1, check) && isScramble(t2, rest)) return true;
                }
                
                // check from the tail.
                check = s2.substring(l - i, l);
                rest = s2.substring(0, l - i);
                if(containsSameChars(t1, check)) {
                    if(isScramble(t1, check) && isScramble(t2, rest)) return true;
                }
            }
            
            return false;
        }
        
        private boolean containsSameChars(String s1, String s2) {
            char[] c1 = s1.toCharArray();
            char[] c2 = s2.toCharArray();
            
            Arrays.sort(c1);
            Arrays.sort(c2);
            
            return Arrays.equals(c1, c2);
        }
    }
    

    Comment if you know the exact complexity of that solution.


Log in to reply
 

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