Scramble String

Scramble String is a recursion-and-memoization classic. The definition is self-referential — a string is scrambled by splitting it and scrambling each half — so the solution is naturally recursive, and the overlapping subproblems beg for a memo.

The slow way first

The brute force is to literally generate every scramble of s1 and see if s2 is among them. At each level you pick a split point and choose whether to swap, so the number of scrambles explodes — this is exponential and quickly hopeless even for short strings.

The better question: instead of building all scrambles, can I check membership directly? If s2 is a scramble of s1, then there must exist a split where the two halves line up — either straight across or swapped. That turns "generate everything" into "search for one good split."

The idea: try every split, straight or swapped

For some split index i, s1 is scramble-equal to s2 when either:

• no swap — s1[:i] ~ s2[:i] and s1[i:] ~ s2[i:], or
• swapped — s1[:i] ~ s2[n-i:] and s1[i:] ~ s2[:n-i].

The ~ is the same scramble relation, applied recursively to smaller pieces. Two base cases stop the recursion: equal strings always match, and strings with different letter counts never match (a cheap pruning check). Because the same (s1, s2) pair comes up again and again, we memoize every result.

The key insight: a swap reverses which half of s2 each half of s1 must match, which is why the swapped branch compares s1's left against s2's right end.

Walk through it

Step through the animation. The top row is s1, the bottom row is s2, and the split pointer marks where we cut s1. The cut at i = 1 fails fast. Sliding it to i = 2 gives halves "gr" and "eat": the swapped branch matches "gr" to "rg" (just g~g and r~r), and the right halves "eat" and "eat" are already equal. One split worked, so the answer is True.

Pseudocode

function scramble(s1, s2):
    if s1 == s2: return True            # base: identical
    if sorted(s1) != sorted(s2):        # base: different letters
        return False
    for each split i from 1 to len-1:
        # straight pairing
        if scramble(s1[:i], s2[:i]) and scramble(s1[i:], s2[i:]):
            return True
        # swapped pairing
        if scramble(s1[:i], s2[n-i:]) and scramble(s1[i:], s2[:n-i]):
            return True
    return False
    # memoize every (s1, s2) result so it is computed once

The Python solution

def is_scramble(s1, s2, memo={}):
    if s1 == s2:
        return True
    if sorted(s1) != sorted(s2):
        return False
    n = len(s1)
    for i in range(1, n):
        if (is_scramble(s1[:i], s2[:i]) and
                is_scramble(s1[i:], s2[i:])):
            return True
        if (is_scramble(s1[:i], s2[n - i:]) and
                is_scramble(s1[i:], s2[:n - i])):
            return True
    return False

• if s1 == s2 is the success base case — identical strings are trivially scrambles.
• if sorted(s1) != sorted(s2) prunes hard: different letter multisets can never match, so we bail before any recursion.
• The loop tries every split point i from 1 to n-1.
• The no-swap check pairs left-with-left and right-with-right.
• The swapped check pairs s1's left with s2's last i characters, and s1's right with s2's first n-i characters.
• The first split that satisfies either pairing returns True; if none do, the strings are not scrambles. A memo on (s1, s2) keeps each pair from being recomputed.

Complexity

A subproblem is fixed by a start index in s1, a start index in s2, and a length — that is O(n^3) distinct states, and each does O(n) work over the split points. Memoization is what turns the exponential search into a polynomial one.

When this pattern shows up

Practice