LeetCode 87: Scramble String

Problem Restatement

We are given two strings:

s1: str
s2: str

Both strings have the same length.

We need to return whether s2 can be produced by scrambling s1.

A scramble is formed recursively:

1. If the string length is 1, stop.
2. Otherwise, split the string into two non-empty parts.
3. Either keep the two parts in the same order or swap them.
4. Apply the same process recursively to each part.

The official problem asks whether s2 is a scrambled string of s1. The constraints are s1.length == s2.length, 1 <= s1.length <= 30, and both strings contain lowercase English letters.

Input and Output

Function shape:

class Solution:
    def isScramble(self, s1: str, s2: str) -> bool:
        ...

Examples

Example 1:

s1 = "great"
s2 = "rgeat"

One valid scramble is:

"great"
-> "gr" + "eat"
-> "rg" + "eat"
-> "rgeat"

So the answer is:

True

Example 2:

s1 = "abcde"
s2 = "caebd"

No sequence of recursive splits and swaps can transform s1 into s2.

Answer:

False

Example 3:

s1 = "a"
s2 = "a"

A length-one string is already itself.

Answer:

True

First Thought: Try Every Split Recursively

A scramble always comes from splitting a string into two non-empty parts.

For a string of length n, possible split lengths are:

1, 2, ..., n - 1

For each split length, there are two cases.

Case 1: no swap.

s1_left  -> s2_left
s1_right -> s2_right

Case 2: swap.

s1_left  -> s2_right
s1_right -> s2_left

If either case works for any split, then s2 is a scramble of s1.

A direct recursive implementation follows this definition, but it repeats the same substring comparisons many times.

Key Insight

The same subproblem appears repeatedly.

For example, while checking larger substrings, we may ask the same question many times:

Is s1[i:i + length] a scramble of s2[j:j + length]?

So we memoize this state.

Define:

dfs(i, j, length)

to mean:

s1[i:i + length] can scramble into s2[j:j + length]

The final answer is:

dfs(0, 0, len(s1))

This avoids copying substrings in every recursive call and gives us a finite dynamic programming state space.

Important Pruning

Before trying every split, compare character counts.

If two substrings do not contain the same multiset of characters, one cannot be a scramble of the other.

For example:

"abc"
"abd"

These cannot match because one has c and the other has d.

In code, for this problem size, we can use:

Counter(s1[i:i + length]) != Counter(s2[j:j + length])

If the counts differ, return False immediately.

This pruning removes many impossible branches.

Recurrence

For each split size:

split = 1, 2, ..., length - 1

There are two possibilities.

No swap:

dfs(i, j, split)
and
dfs(i + split, j + split, length - split)

Swap:

dfs(i, j + length - split, split)
and
dfs(i + split, j, length - split)

If either possibility is true, return True.

If no split works, return False.

Algorithm

Let:

n = len(s1)

Define a memoized recursive function:

dfs(i, j, length)

Inside dfs:

1. If the substrings are equal, return True.
2. If their character counts differ, return False.
3. Try every split length from 1 to length - 1.
4. Check the no-swap case.
5. Check the swap case.
6. If any case works, return True.
7. Otherwise, return False.

Return:

dfs(0, 0, n)

Walkthrough

Use:

s1 = "great"
s2 = "rgeat"

Start with:

dfs(0, 0, 5)

This compares:

"great"
"rgeat"

They have the same characters, so we try splits.

Try split 2:

s1 = "gr" + "eat"
s2 = "rg" + "eat"

No-swap case asks:

dfs("gr", "rg")
and
dfs("eat", "eat")

The second part is immediately true.

Now check:

dfs("gr", "rg")

Split 1:

"g" + "r"
"r" + "g"

The swap case works:

"g" -> "g"
"r" -> "r"

So "gr" can scramble into "rg".

Therefore, "great" can scramble into "rgeat".

The answer is:

True

Correctness

The recursive definition matches the scramble operation exactly.

If the algorithm returns True, then either the two substrings are equal, or it found a split where both resulting parts can be matched recursively. In the no-swap case, the left part maps to the left part and the right part maps to the right part. In the swap case, the left part maps to the right part and the right part maps to the left part. Both are valid scramble operations. Therefore, a True result corresponds to a valid scramble.

If s2 is a valid scramble of s1, then its first scramble step uses some split. That split either keeps the two parts in order or swaps them. The algorithm tries every possible split and both order choices. Then it recursively checks the two smaller scramble relationships. By induction on substring length, those smaller relationships will return True. Therefore, the algorithm will find the valid split and return True.

The character-count check cannot remove a valid answer because scrambling only rearranges characters. It never changes character counts.

Therefore, the algorithm returns True exactly when s2 is a scrambled string of s1.

Complexity

Let:

n = len(s1)

There are O(n^3) states because i, j, and length determine one state.

For each state, we may try O(n) splits.

Using substring Counter checks adds extra cost, but with n <= 30 it is still acceptable. The usual DP bound for the recurrence is:

With direct substring counter construction, the constant factor is larger.

Implementation

from collections import Counter
from functools import cache

class Solution:
    def isScramble(self, s1: str, s2: str) -> bool:
        n = len(s1)

        @cache
        def dfs(i: int, j: int, length: int) -> bool:
            a = s1[i:i + length]
            b = s2[j:j + length]

            if a == b:
                return True

            if Counter(a) != Counter(b):
                return False

            for split in range(1, length):
                if (
                    dfs(i, j, split)
                    and dfs(i + split, j + split, length - split)
                ):
                    return True

                if (
                    dfs(i, j + length - split, split)
                    and dfs(i + split, j, length - split)
                ):
                    return True

            return False

        return dfs(0, 0, n)

Code Explanation

We use cache to memoize recursive states:

@cache
def dfs(i: int, j: int, length: int) -> bool:

The state means:

s1[i:i + length]
s2[j:j + length]

If the substrings are already equal, no more scrambling is needed:

if a == b:
    return True

Then we check whether the two substrings have the same character counts:

if Counter(a) != Counter(b):
    return False

If they do not, no split can fix that.

Then we try every non-empty split:

for split in range(1, length):

No-swap case:

dfs(i, j, split)
and
dfs(i + split, j + split, length - split)

Swap case:

dfs(i, j + length - split, split)
and
dfs(i + split, j, length - split)

If either case works, return True.

If no split works:

return False

The final call compares the full strings:

return dfs(0, 0, n)

Testing

def run_tests():
    s = Solution()

    assert s.isScramble("great", "rgeat") is True
    assert s.isScramble("abcde", "caebd") is False
    assert s.isScramble("a", "a") is True

    assert s.isScramble("abc", "bca") is True
    assert s.isScramble("abc", "def") is False
    assert s.isScramble("aa", "aa") is True
    assert s.isScramble("ab", "ba") is True
    assert s.isScramble("abcd", "badc") is True

    print("all tests passed")

run_tests()

Test meaning: