Java 3ms, beat 98.86%


  • 0
    J

    it's same solution, but instead of using substring, use character array to avoid creating new string.

        public boolean isScramble(String s1, String s2) {
            if (s1 == null && s2 == null) return true;
            if (s1.length() != s2.length()) return false;
            return isScramble(s1.toCharArray(), s2.toCharArray(), 0, 0, s1.length());
        }
        
        private boolean isScramble(char[] cs1, char[] cs2, int s1, int s2, int len) {
            if (len == 0) return true;
            boolean same = true;
            for (int i = 0; i < len; i++) {
                if (cs1[s1 + i] != cs2[s2 + i]) {
                    same = false;
                    break;
                }
            }
            if (same) return true;
            int[] letters = new int[26];
            for (int i = 0; i < len; i++) {
                letters[cs1[s1 + i] - 'a']++;
                letters[cs2[s2 + i] - 'a']--;
            }
            for (int cnt : letters) if (cnt != 0) return false;
            for (int i = 1; i < len; i++) {
                if (isScramble(cs1, cs2, s1, s2, i) && isScramble(cs1, cs2, s1 + i, s2 + i, len - i)) return true;
                if (isScramble(cs1, cs2, s1, s2 + len - i, i) && isScramble(cs1, cs2, s1 + i, s2, len - i)) return true;
            }
            return false;
        }
    

Log in to reply
 

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