Scramble String

We define a scramble process on a string recursively: split it at some point and optionally swap the two halves, then recursively scramble each part. Given s1 and s2, return true if s2 is a scramble of s1.

Example 1

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

Example 2

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

Solution Approach

Use memoization: isScramble(s1,s2) tries all split points. For each split at k: either (no swap) first k of s1 matches first k of s2 AND rest matches; or (swap) first k of s1 matches last k of s2 AND rest matches.

Base: if s1==s2 return true. If sorted chars differ return false.
For each split length k from 1 to n-1:
No swap: isScramble(s1[0..k], s2[0..k]) && isScramble(s1[k..], s2[k..]).
Swap: isScramble(s1[0..k], s2[n-k..]) && isScramble(s1[k..], s2[0..n-k]).

Java

import java.util.*;

class Solution {
    Map<String,Boolean> memo = new HashMap<>();

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

Time Complexity: O(N^4) with memoization
Space Complexity: O(N^3) memo states