87. Scramble String

String
Dynamic Programming
Recursion
Memoization

TIME

O(n^4)

SPACE

O(n^3)

Intuition

The scrambling process is recursive by definition, so the natural question to ask is also recursive: given a substring of s1 and a substring of s2 of the same length, can the first scramble into the second?

At the top level the algorithm split s1 somewhere and then either kept the halves in place or swapped them. That gives exactly two shapes to check for each split point k:

No swap: the first k characters of s1's piece scramble into the first k of s2's piece, and the rest scramble into the rest.
Swap: the first k of s1's piece scramble into the last k of s2's piece, and the remaining len - k of s1 scramble into the first len - k of s2.

Either shape succeeding for any k means the answer is yes.

Two things make this tractable. The state (i, j, len) has only O(n^3) distinct values, so memoization caps the work. And a scramble is a permutation of characters, so if two pieces don't have the same letter multiset, no split can possibly work, checking that first prunes the overwhelming majority of branches before any recursion happens.

Approach

Define solve(i, j, len) = whether s1[i : i+len] scrambles into s2[j : j+len].

If the two substrings are identical, return true.
If their character counts differ, return false (fast rejection).
For each split k from 1 to len - 1:
- no swap: solve(i, j, k) and solve(i+k, j+k, len-k)
- swap: solve(i, j+len-k, k) and solve(i+k, j, len-k)
- return true if either holds.
Return false; memoize every (i, j, len) result.

The answer is solve(0, 0, n).

Complexity

Time: O(n^4), O(n^3) states, each trying O(n) splits; the count-mismatch pruning makes the real cost far lower
Space: O(n^3), the memo table, plus O(n) recursion depth

Edge Cases

Length 1 → strings must be equal (Example 3)
Equal strings at any level short-circuit to true without splitting
Anagrams are necessary but not sufficient (Example 2 is an anagram that still fails)
Different multisets fail instantly via the count check, never touching the recursion
The swap branch maps s1's prefix to s2's suffix; getting that offset wrong is the classic bug here

Code

from functools import lru_cache


class Solution:
    def isScramble(self, s1: str, s2: str) -> bool:
        """
        87. Scramble String
        Time: O(n^4)
        Space: O(n^3)
        """
        n = len(s1)
        if n != len(s2):
            return False

        @lru_cache(maxsize=None)
        def solve(i: int, j: int, length: int) -> bool:
            # can s1[i:i+length] scramble into s2[j:j+length]?
            a = s1[i:i + length]
            b = s2[j:j + length]
            if a == b:
                return True
            if sorted(a) != sorted(b):
                return False  # different letters: no split can work

            for k in range(1, length):
                # halves kept in order
                if solve(i, j, k) and solve(i + k, j + k, length - k):
                    return True
                # halves swapped: s1's prefix lands on s2's suffix
                if solve(i, j + length - k, k) and solve(i + k, j, length - k):
                    return True
            return False

        result = solve(0, 0, n)
        solve.cache_clear()
        return result

/**
 * 87. Scramble String
 * Time: O(n^4)
 * Space: O(n^3)
 */
class Solution {
    private String s1, s2;
    private Boolean[][][] memo; // [i][j][length], null = not yet computed

    public boolean isScramble(String s1, String s2) {
        int n = s1.length();
        if (n != s2.length()) {
            return false;
        }
        this.s1 = s1;
        this.s2 = s2;
        memo = new Boolean[n][n][n + 1];
        return solve(0, 0, n);
    }

    /** Can s1[i, i+length) scramble into s2[j, j+length)? */
    private boolean solve(int i, int j, int length) {
        if (memo[i][j][length] != null) {
            return memo[i][j][length];
        }

        boolean result;
        if (s1.regionMatches(i, s2, j, length)) {
            result = true;
        } else if (!sameLetters(i, j, length)) {
            result = false; // different letters: no split can work
        } else {
            result = false;
            for (int k = 1; k < length && !result; k++) {
                // halves kept in order
                if (solve(i, j, k) && solve(i + k, j + k, length - k)) {
                    result = true;
                }
                // halves swapped: s1's prefix lands on s2's suffix
                else if (solve(i, j + length - k, k) && solve(i + k, j, length - k)) {
                    result = true;
                }
            }
        }

        memo[i][j][length] = result;
        return result;
    }

    private boolean sameLetters(int i, int j, int length) {
        int[] count = new int[26];
        for (int t = 0; t < length; t++) {
            count[s1.charAt(i + t) - 'a']++;
            count[s2.charAt(j + t) - 'a']--;
        }
        for (int c : count) {
            if (c != 0) {
                return false;
            }
        }
        return true;
    }
}