# LeetCode 87: Scramble String

## Problem Restatement

We are given two strings:

```python
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

| Item | Meaning |
|---|---|
| Input | Two strings `s1` and `s2` |
| Output | `True` if `s2` is a scramble of `s1`, otherwise `False` |
| Length rule | `s1` and `s2` have the same length |
| Split rule | Each split creates two non-empty substrings |
| Operation | At each split, we may swap or keep the two parts |

Function shape:

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

## Examples

Example 1:

```python
s1 = "great"
s2 = "rgeat"
```

One valid scramble is:

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

So the answer is:

```python
True
```

Example 2:

```python
s1 = "abcde"
s2 = "caebd"
```

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

Answer:

```python
False
```

Example 3:

```python
s1 = "a"
s2 = "a"
```

A length-one string is already itself.

Answer:

```python
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:

```python
1, 2, ..., n - 1
```

For each split length, there are two cases.

Case 1: no swap.

```python
s1_left  -> s2_left
s1_right -> s2_right
```

Case 2: swap.

```python
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:

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

So we memoize this state.

Define:

```python
dfs(i, j, length)
```

to mean:

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

The final answer is:

```python
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:

```python
"abc"
"abd"
```

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

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

```python
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:

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

There are two possibilities.

No swap:

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

Swap:

```python
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:

```python
n = len(s1)
```

Define a memoized recursive function:

```python
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:

```python
dfs(0, 0, n)
```

## Walkthrough

Use:

```python
s1 = "great"
s2 = "rgeat"
```

Start with:

```python
dfs(0, 0, 5)
```

This compares:

```python
"great"
"rgeat"
```

They have the same characters, so we try splits.

Try split `2`:

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

No-swap case asks:

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

The second part is immediately true.

Now check:

```python
dfs("gr", "rg")
```

Split `1`:

```python
"g" + "r"
"r" + "g"
```

The swap case works:

```python
"g" -> "g"
"r" -> "r"
```

So `"gr"` can scramble into `"rg"`.

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

The answer is:

```python
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:

```python
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:

| Metric | Value | Why |
|---|---|---|
| Time | `O(n^4)` | `O(n^3)` states and up to `O(n)` split choices per state |
| Space | `O(n^3)` | Memoization stores states |

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

## Implementation

```python
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:

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

The state means:

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

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

```python
if a == b:
    return True
```

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

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

If they do not, no split can fix that.

Then we try every non-empty split:

```python
for split in range(1, length):
```

No-swap case:

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

Swap case:

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

If either case works, return `True`.

If no split works:

```python
return False
```

The final call compares the full strings:

```python
return dfs(0, 0, n)
```

## Testing

```python
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:

| Test | Why |
|---|---|
| `"great", "rgeat"` | Main true example |
| `"abcde", "caebd"` | Main false example |
| `"a", "a"` | Length-one base case |
| `"abc", "bca"` | Valid through recursive split and swap |
| `"abc", "def"` | Character counts differ |
| `"aa", "aa"` | Repeated equal letters |
| `"ab", "ba"` | Single swap |
| `"abcd", "badc"` | Multiple recursive swaps |