# Scramble String
**Difficulty:** HARD
[External](https://leetcode.com/problems/scramble-string)
Canonical: https://scaleengineer.com/dsa/problems/scramble-string
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String
**Companies:** [Amazon](https://scaleengineer.com/companies/amazon), [Google](https://scaleengineer.com/companies/google), [Media.net](https://scaleengineer.com/companies/media.net), [Rubrik](https://scaleengineer.com/companies/rubrik), [Darwinbox](https://scaleengineer.com/companies/darwinbox)
---
## 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:  
  * 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`.
  * **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`.
  * 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`.

**Example 1:**

**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.

**Example 2:**

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

**Example 3:**

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

**Constraints:**

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

# Approaches
## Brute-force Recursion
This approach directly translates the problem's recursive definition into a function. It explores every possible way `s1` can be partitioned and potentially swapped, checking if any of these recursive constructions result in `s2`. While conceptually simple, it's computationally very expensive.
**Time:** O(n * C_n) ~ O(4^n / n^(3/2)) · **Space:** O(n)
**Pros:** Simple to understand and implement as it directly models the problem description.
**Cons:** Extremely inefficient due to a massive number of overlapping subproblems.; Leads to an exponential time complexity, which will cause a 'Time Limit Exceeded' error for the given constraints.
### Explanation
The core of this method is a recursive function `isScramble(s1, s2)`. The base case for the recursion is when the two strings are equal, in which case we return `true`. A crucial optimization, or pruning step, is to first check if `s1` and `s2` are anagrams. If their character counts don't match, it's impossible for one to be a scrambled version of the other, so we can immediately return `false`. For the recursive step, the function iterates through all possible split points of the string `s1`. For each split, it considers two scenarios based on the problem definition: the two substrings are not swapped, or they are swapped. It then makes recursive calls to check if the corresponding substrings are themselves scrambled. If any of these recursive explorations yield a valid scrambling, the function returns `true`. If all possibilities are exhausted without success, it returns `false`.

```java
class Solution {
    public boolean isScramble(String s1, String s2) {
        if (s1.equals(s2)) {
            return true;
        }
        if (s1.length() != s2.length()) {
            return false;
        }

        // Anagram check
        int[] letters = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            letters[s1.charAt(i) - 'a']++;
            letters[s2.charAt(i) - 'a']--;
        }
        for (int i = 0; i < 26; i++) {
            if (letters[i] != 0) {
                return false;
            }
        }

        int n = s1.length();
        for (int i = 1; i < n; i++) {
            // Case 1: No swap
            if (isScramble(s1.substring(0, i), s2.substring(0, i)) &&
                isScramble(s1.substring(i), s2.substring(i))) {
                return true;
            }
            // Case 2: Swap
            if (isScramble(s1.substring(0, i), s2.substring(n - i)) &&
                isScramble(s1.substring(i), s2.substring(0, n - i))) {
                return true;
            }
        }
        return false;
    }
}
```
### Algorithm
*   Define a recursive function `isScramble(s1, s2)`.
*   **Base Case:** If `s1` and `s2` are identical, return `true`.
*   **Pruning:** Check if `s1` and `s2` are anagrams. This can be done by sorting or using a frequency map. If they are not anagrams, they cannot be scrambled versions of each other, so return `false`.
*   **Recursive Step:** Iterate through all possible split points `i` from `1` to `s1.length() - 1`.
    *   For each split `i`, `s1` is divided into `s1_left = s1.substring(0, i)` and `s1_right = s1.substring(i)`.
    *   Check two possibilities for `s2`:
        1.  **No-swap:** `s2` is split at the same point `i` into `s2_left` and `s2_right`. Recursively check if `isScramble(s1_left, s2_left)` AND `isScramble(s1_right, s2_right)`.
        2.  **Swap:** `s1_left` is compared with the end part of `s2` of the same length, and `s1_right` with the beginning part. Recursively check if `isScramble(s1_left, s2.substring(n-i))` AND `isScramble(s1_right, s2.substring(0, n-i))`.
    *   If any of these checks return `true`, it means a valid scramble is found, so return `true`.
*   If the loop completes without finding a valid scramble, return `false`.

## Recursion with Memoization (Top-Down DP)
This approach improves upon the brute-force recursion by using memoization, a top-down dynamic programming technique. It avoids recomputing results for the same subproblems by storing their outcomes in a cache. A subproblem is defined by the starting indices and length of the substrings being compared.
**Time:** O(n^4) · **Space:** O(n^3)
**Pros:** Drastically more efficient than brute-force by eliminating redundant computations.; Guarantees that each subproblem is solved only once.; Sufficiently fast to pass the given constraints.
**Cons:** Requires significant extra space, O(n^3), for the memoization table.; The logic is slightly more complex than brute-force due to managing the cache.
### Explanation
The brute-force solution is inefficient because it repeatedly solves the same subproblems. For instance, checking if `"eat"` is a scramble of `"tea"` might be required multiple times through different recursive paths. Memoization addresses this by caching the result of each unique subproblem `isScramble(substring1, substring2)`.

A subproblem can be uniquely identified by a tuple `(i1, i2, len)`, representing the check for `s1`'s substring starting at `i1` and `s2`'s substring starting at `i2`, both of length `len`. We use a 3D array, `memo[n][n][n+1]`, to store these results. Each entry can hold one of three states: `true`, `false`, or `null` (not yet computed).

The recursive function first checks this memoization table. If a result for the current subproblem `(i1, i2, len)` exists, it's returned immediately. Otherwise, the computation proceeds as in the brute-force approach. Once the result is computed, it's stored in `memo[i1][i2][len]` before being returned, ensuring that this specific subproblem is never solved again.

```java
class Solution {
    private Boolean[][][] memo;
    private String s1;
    private String s2;

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

    private boolean solve(int i1, int i2, int len) {
        if (memo[i1][i2][len] != null) {
            return memo[i1][i2][len];
        }
        if (s1.substring(i1, i1 + len).equals(s2.substring(i2, i2 + len))) {
            return memo[i1][i2][len] = true;
        }

        int[] letters = new int[26];
        for (int i = 0; i < len; i++) {
            letters[s1.charAt(i1 + i) - 'a']++;
            letters[s2.charAt(i2 + i) - 'a']--;
        }
        for (int count : letters) {
            if (count != 0) {
                return memo[i1][i2][len] = false;
            }
        }

        for (int k = 1; k < len; k++) {
            if ((solve(i1, i2, k) && solve(i1 + k, i2 + k, len - k)) ||
                (solve(i1, i2 + len - k, k) && solve(i1 + k, i2, len - k))) {
                return memo[i1][i2][len] = true;
            }
        }

        return memo[i1][i2][len] = false;
    }
}
```
### Algorithm
*   Define a recursive helper function `solve(i1, i2, len)` that checks if `s1.substring(i1, i1+len)` is a scramble of `s2.substring(i2, i2+len)`.
*   Use a 3D array `memo[n][n][n+1]` to store the results of subproblems. Initialize it with a value indicating 'not computed' (e.g., `null`).
*   In `solve(i1, i2, len)`:
    *   First, check if `memo[i1][i2][len]` has a stored result. If so, return it.
    *   Check for base cases and anagrams as in the brute-force approach.
    *   Iterate through split lengths `k` from `1` to `len-1`.
    *   Make recursive calls for the 'swap' and 'no-swap' cases: `solve(i1, i2, k)`, `solve(i1+k, i2+k, len-k)`, etc.
    *   If a valid scramble is found, store `true` in `memo[i1][i2][len]`, and return `true`.
*   If the loop finishes, store `false` in `memo[i1][i2][len]` and return `false`.
*   The initial call is `solve(0, 0, n)`.

## Bottom-Up Dynamic Programming
This approach is an iterative, bottom-up version of the dynamic programming solution. It systematically builds the solution from the smallest subproblems (substrings of length 1) up to the original problem (the full strings). By filling a DP table iteratively, it avoids the overhead and potential stack depth issues of recursion.
**Time:** O(n^4) · **Space:** O(n^3)
**Pros:** Generally the most efficient solution in practice due to avoiding recursion overhead.; Guaranteed to be fast enough for the given constraints.
**Cons:** Can be harder to reason about and implement correctly compared to the top-down approach.; Uses a large amount of memory, O(n^3), for the DP table.
### Explanation
Instead of starting from the top (the full string) and breaking it down, the bottom-up approach starts from the bottom (substrings of length 1) and builds up. We use a 3D DP table, `dp[len][i][j]`, which stores whether `s1.substring(i, i+len)` is a scramble of `s2.substring(j, j+len)`.

The solution is built by iterating through substring lengths (`len`) from 1 to `n`. For each length, we iterate through all possible start indices `i` and `j`. The base cases are for `len = 1`, where `dp[1][i][j]` is true only if the characters `s1.charAt(i)` and `s2.charAt(j)` are the same. For lengths greater than 1, we calculate `dp[len][i][j]` by looking up the results for smaller lengths, which are guaranteed to have been computed already. We check all possible split points `k` and see if either the 'no-swap' or 'swap' condition holds true based on the values in our `dp` table. The final answer is found in `dp[n][0][0]`, which represents the solution for the original full strings.

```java
class Solution {
    public boolean isScramble(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return false;
        }
        int n = s1.length();
        if (n == 0) {
            return true;
        }
        // dp[len][i][j] is true if s1.substring(i, i+len) is a scramble of s2.substring(j, j+len)
        boolean[][][] dp = new boolean[n + 1][n][n];

        // Base case: len = 1
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[1][i][j] = (s1.charAt(i) == s2.charAt(j));
            }
        }

        // Fill DP table for len from 2 to n
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                for (int j = 0; j <= n - len; j++) {
                    for (int k = 1; k < len; k++) {
                        // No-swap case
                        boolean noSwap = dp[k][i][j] && dp[len - k][i + k][j + k];
                        // Swap case
                        boolean swap = dp[k][i][j + len - k] && dp[len - k][i + k][j];
                        
                        if (noSwap || swap) {
                            dp[len][i][j] = true;
                            break; // Found a valid split
                        }
                    }
                }
            }
        }
        return dp[n][0][0];
    }
}
```
### Algorithm
*   Create a 3D boolean DP table `dp[len][i][j]`, where `dp[len][i][j]` will be `true` if `s1.substring(i, i+len)` is a scramble of `s2.substring(j, j+len)`.
*   Iterate over the substring length `len` from `1` to `n`.
*   Inside, iterate over all possible starting indices `i` in `s1` and `j` in `s2`.
*   **Base Case (`len = 1`):** `dp[1][i][j] = (s1.charAt(i) == s2.charAt(j))`.
*   **Inductive Step (`len > 1`):** To compute `dp[len][i][j]`, iterate through all possible split lengths `k` from `1` to `len - 1`.
    *   Check the two conditions using previously computed values from the `dp` table:
        1.  **No-swap:** `dp[k][i][j] && dp[len-k][i+k][j+k]`
        2.  **Swap:** `dp[k][i][j+len-k] && dp[len-k][i+k][j]`
    *   If either condition is true for any `k`, set `dp[len][i][j] = true` and break the inner loop over `k`.
*   The final answer is the value of `dp[n][0][0]`.

# Solutions
### CSharp

```csharp
public class Solution { private string s1 ; private string s2 ; private int [,,] f ; public bool IsScramble ( string s1 , string s2 ) { int n = s1 . Length ; this . s1 = s1 ; this . s2 = s2 ; f = new int [ n , n , n + 1 ]; return dfs ( 0 , 0 , n ); } private bool dfs ( int i , int j , int k ) { if ( f [ i , j , k ] != 0 ) { return f [ i , j , k ] == 1 ; } if ( k == 1 ) { return s1 [ i ] == s2 [ j ]; } for ( int h = 1 ; h < k ; ++ h ) { if ( dfs ( i , j , h ) && dfs ( i + h , j + h , k - h )) { f [ i , j , k ] = 1 ; return true ; } if ( dfs ( i , j + k - h , h ) && dfs ( i + h , j , k - h )) { f [ i , j , k ] = 1 ; return true ; } } f [ i , j , k ] = - 1 ; return false ; } }
```

### Java

```java
class Solution { private Boolean [][][] f ; private String s1 ; private String s2 ; public boolean isScramble ( String s1 , String s2 ) { int n = s1 . length (); this . s1 = s1 ; this . s2 = s2 ; f = new Boolean [ n ][ n ][ n + 1 ]; return dfs ( 0 , 0 , n ); } private boolean dfs ( int i , int j , int k ) { if ( f [ i ][ j ][ k ] != null ) { return f [ i ][ j ][ k ]; } if ( k == 1 ) { return s1 . charAt ( i ) == s2 . charAt ( j ); } for ( int h = 1 ; h < k ; ++ h ) { if ( dfs ( i , j , h ) && dfs ( i + h , j + h , k - h )) { return f [ i ][ j ][ k ] = true ; } if ( dfs ( i + h , j , k - h ) && dfs ( i , j + k - h , h )) { return f [ i ][ j ][ k ] = true ; } } return f [ i ][ j ][ k ] = false ; } }
```

### CPP

```cpp
class Solution { public: bool isScramble ( string s1 , string s2 ) { int n = s1 . size (); int f [ n ][ n ][ n + 1 ]; memset ( f , - 1 , sizeof ( f )); function < bool ( int , int , int ) > dfs = [ & ]( int i , int j , int k ) -> int { if ( f [ i ][ j ][ k ] != - 1 ) { return f [ i ][ j ][ k ] == 1 ; } if ( k == 1 ) { return s1 [ i ] == s2 [ j ]; } for ( int h = 1 ; h < k ; ++ h ) { if ( dfs ( i , j , h ) && dfs ( i + h , j + h , k - h )) { return f [ i ][ j ][ k ] = true ; } if ( dfs ( i + h , j , k - h ) && dfs ( i , j + k - h , h )) { return f [ i ][ j ][ k ] = true ; } } return f [ i ][ j ][ k ] = false ; }; return dfs ( 0 , 0 , n ); } };
```

### Python

```python
class Solution : def isScramble ( self , s1 : str , s2 : str ) -> bool : @ cache def dfs ( i : int , j : int , k : int ) -> bool : if k == 1 : return s1 [ i ] == s2 [ j ] for h in range ( 1 , k ): if dfs ( i , j , h ) and dfs ( i + h , j + h , k - h ): return True if dfs ( i + h , j , k - h ) and dfs ( i , j + k - h , h ): return True return False return dfs ( 0 , 0 , len ( s1 ))
```