87. Scramble String

[TODO] Optimization
二刷

9.60 %
class Solution {
    public boolean isScramble(String s1, String s2) {
        if (s1 == null && s2 == null) return true;
        if (s1 == null || s2 == null || s1.length() != s2.length()) return false;
        if (s1.equals(s2)) {
            return true;
        }
        int[] counter = new int[26];
        int len = s1.length();
        System.out.println(s1 + " " + s2);
        for (int i = 0; i < len; i++) {
            counter[s1.charAt(i) - 'a']++;
            counter[s2.charAt(i) - 'a']--;
        }
        for (int i = 0; i < 26; i++) {
            if (counter[i] != 0) return false;
        }
        for (int i = 1; i < len; i++) {
            if (isScramble(s1.substring(0, i), s2.substring(0, i))
                && isScramble(s1.substring(i), s2.substring(i))
                || isScramble(s1.substring(0, i), s2.substring(len - i))
                && isScramble(s1.substring(i), s2.substring(0, len - i))) {
                return true;
            }
        }
        return false;
    }
}

一刷
8.19 %
class Solution {
    public boolean isScramble(String s1, String s2) {
        if (s1.length() != s2.length()) return false;
        if (s1.equals(s2)) {
            return true;
        }
        int length = s1.length();
        if (length == 1) {
            return false;
        }
        Map<Character, Integer> counter = new HashMap<>();
        for (int i = 0; i < s1.length(); i++) {
            counter.put(s1.charAt(i), counter.getOrDefault(s1.charAt(i), 0) + 1);
            counter.put(s2.charAt(i), counter.getOrDefault(s2.charAt(i), 0) - 1);
        }
        for(Integer count : counter.values()) {
            if (count != 0) {
                return false;
            }
        }
        //start mid    end = 4
        // 1     2  3
        // 1  2      3
        // [start, mid) [mid, end)
        // [start, start + end - mid) [start - mid + end, end)
        for (int mid = 1; mid < length; mid++) {
            boolean left1 = isScramble(s1.substring(0, mid), s2.substring(0, mid));
            boolean right1 = isScramble(s1.substring(mid, length), s2.substring(mid, length));
            boolean left2 = isScramble(s1.substring(0, mid), s2.substring(length - mid, length));
            boolean right2 = isScramble(s1.substring(mid, length), s2.substring(0, length - mid));
            if (left1 && right1 || left2 && right2) {
                return true;
            }
        }
        return false;
    }
}