> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Scramble String Python Solution with Tests

> Tested Python solution for LeetCode 87 with 26 pytest cases. Generate a practice environment with lcpy.

LeetCode 87, [Hard](/catalog/hard). Topics: [String](/catalog/topics/string), [Dynamic Programming](/catalog/topics/dynamic-programming). [View on LeetCode](https://leetcode.com/problems/scramble-string/description/).

Generate this problem as a practice environment: tested reference solution, 26 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 87   # by problem number
lcpy gen -s scramble_string   # by problem name
```

## Problem

We can scramble a string s to get a string t using the following algorithm:

1. If the length of the string is 1, stop.
2. If the length of the string is > 1, do the following:
   1. Split the string into two non-empty substrings at a random index, i.e., if the string is `s`, divide it to `x` and `y` where `s = x + y`.
   2. Randomly decide to swap the two substrings or to keep them in the same order. i.e., after this step, `s` may become `s = x + y` or `s = y + x`.
   3. Apply step 1 recursively on each of the two substrings `x` and `y`.

Given two strings `s1` and `s2` of **the same length**, return `true` if `s2` is a scrambled string of `s1`, otherwise, return `false`.

### Examples

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

**Explanation:** One possible scenario applied on `s1` is:
`"great" --> "gr/eat"` // divide at random index.
`"gr/eat" --> "gr/eat"` // random decision is not to swap the two substrings and keep them in order.
`"gr/eat" --> "g/r / e/at"` // apply the same algorithm recursively on both substrings. divide at random index each of them.
`"g/r / e/at" --> "r/g / e/at"` // random decision was to swap the first substring and to keep the second substring in the same order.
`"r/g / e/at" --> "r/g / e/ a/t"` // again apply the algorithm recursively, divide "at" to "a/t".
`"r/g / e/ a/t" --> "r/g / e/ a/t"` // random decision is to keep both substrings in the same order.
The algorithm stops now, and the result string is `"rgeat"` which is `s2`.
As one possible scenario led `s1` to be scrambled to `s2`, we return `true`.

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

```
Input: s1 = "a", s2 = "a"
Output: true
```

### Constraints

* s1.length == s2.length
* 1 \<= s1.length \<= 30
* s1 and s2 consist of lowercase English letters.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/scramble_string/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/scramble_string/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(n^4) substring pairs times O(n) split points, memoized
    # Space: O(n^2) memo entries over substring pairs

    def is_scramble(self, s1: str, s2: str) -> bool:
        if len(s1) != len(s2):
            return False
        memo: dict[tuple[str, str], bool] = {}
        return self.solve(s1, s2, memo)

    def solve(self, s1: str, s2: str, memo: dict[tuple[str, str], bool]) -> bool:
        if s1 == s2:
            return True
        if sorted(s1) != sorted(s2):
            return False
        key = (s1, s2)
        cached = memo.get(key)
        if cached is not None:
            return cached
        n = len(s1)
        result = False
        for i in range(1, n):
            if self.solve(s1[:i], s2[:i], memo) and self.solve(s1[i:], s2[i:], memo):
                result = True
                break
            if self.solve(s1[:i], s2[n - i :], memo) and self.solve(s1[i:], s2[: n - i], memo):
                result = True
                break
        memo[key] = result
        return result
```

## Complexity

| Time | Space |
| - | - |
| O(n^4) substring pairs times O(n) split points, memoized | O(n^2) memo entries over substring pairs |

## Tags


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.