87. Scramble String

class Solution {
    public boolean isScramble(String s1, String s2) {
        if (s1 == null || s2 == null || s1.length() == 0 || s2.length() == 0 || s1.length() != s2.length()) {
            return false;
        }
        if (s1.equals(s2)) {
            return true;
        }

        HashMap<String, Boolean> pairs = new HashMap<>();

        return helper(pairs, s1, s2);
    }

    public boolean helper(HashMap<String, Boolean> pairs, String s1, String s2) {
        String pair = s1 + '#' + s2;

        if (pairs.containsKey(pair)) {
            return pairs.get(pair);
        }

        if (s1.equals(s2)) {
            pairs.put(pair, true);
            return true;
        }
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s1.length(); i++) {
            char c1 = s1.charAt(i);
            char c2 = s2.charAt(i);
            map.put(c1, map.getOrDefault(c1, 0) + 1);
            map.put(c2, map.getOrDefault(c2, 0) - 1);
        }

        for (Map.Entry<Character, Integer> e : map.entrySet()) {
            if (e.getValue() != 0) {
                pairs.put(pair, false);
                return false;
            }
        }

        for (int i = 1; i < s1.length(); i++) {
            if (helper(pairs, s1.substring(0,i), s2.substring(0,i)) && helper(pairs, s1.substring(i), s2.substring(i))) {
                pairs.put(pair, true);
                return true;
            }
            if (helper(pairs, s1.substring(0,i), s2.substring(s2.length()-i)) && helper(pairs, s1.substring(i), s2.substring(0,s2.length()-i))) {
                pairs.put(pair, true);
                return true;
            }
        }
        pairs.put(pair, false);
        return false;
    }
}