Scramble String

Determine if s2 is a scrambled string of s1 (can split and swap subtrees recursively).

Example 1

Input: s1="great", s2="rgeat" → Output: true

Example 2

Input: s1="abcde", s2="caebd" → Output: false

Solution Approach

Memoized recursion: for each split point, check both non-swap and swap cases.

Base case: if s1==s2 return true; if sorted differs return false
For each split length k (1 to n-1)
Case 1 (no swap): isScramble(s1[0..k], s2[0..k]) AND isScramble(s1[k..], s2[k..])
Case 2 (swap): isScramble(s1[0..k], s2[n-k..]) AND isScramble(s1[k..], s2[0..n-k])
Memoize results

Java

public boolean isScramble(String s1, String s2) {
    if (s1.equals(s2)) return true;
    Map<String, Boolean> memo = new HashMap<>();
    return dfs(s1, s2, memo);
}
private boolean dfs(String s1, String s2, Map<String, Boolean> memo) {
    String key = s1 + "#" + s2;
    if (memo.containsKey(key)) return memo.get(key);
    if (s1.equals(s2)) return true;
    char[] a = s1.toCharArray(), b = s2.toCharArray();
    Arrays.sort(a); Arrays.sort(b);
    if (!Arrays.equals(a, b)) { memo.put(key, false); return false; }
    int n = s1.length();
    for (int k = 1; k < n; k++) {
        if (dfs(s1.substring(0,k), s2.substring(0,k), memo) && dfs(s1.substring(k), s2.substring(k), memo) ||
            dfs(s1.substring(0,k), s2.substring(n-k), memo) && dfs(s1.substring(k), s2.substring(0,n-k), memo)) {
            memo.put(key, true); return true;
        }
    }
    memo.put(key, false); return false;
}

Time Complexity: O(n^4)
Space Complexity: O(n^4)