#87 Scramble String - Solution

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

If the length of the string is 1, stop.
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.

Scramble String asks whether one string can be transformed into another by recursively partitioning and swapping substrings. A brute force recursive approach tries every possible split position and checks both cases: swapped and non-swapped substrings. However, this leads to heavy recomputation.

The optimized strategy uses recursion with memoization or dynamic programming. For two substrings of equal length, we attempt all partition points and verify if their left and right segments match either directly or after swapping. Memoization stores results for previously checked substring pairs to avoid repeated work.

Another common method is a 3D DP table where dp[i][j][len] represents whether the substring starting at index i in the first string can form the substring starting at index j in the second string with length len. By iterating through substring lengths and split points, we progressively determine valid scrambles.

This approach significantly reduces redundant checks while maintaining manageable complexity.

Approach	Time Complexity	Space Complexity
Recursion + Memoization	O(n^4)	O(n^3)
Bottom-Up Dynamic Programming	O(n^4)	O(n^3)

Solutions (12)

Recursive Approach with Memoization

This approach uses recursion to explore all possible valid splits and checks if either of the permutations exist. To avoid re-computation, use a dictionary to memoize already computed results for specific substrings.

Time Complexity: O(N^4), where N is the length of the strings.
Space Complexity: O(N^3), used by the memoization array.

C C++Java Python C#JavaScript

1class Solution:
2    def __init__(self):
3        self.memo = {}
4
5    def isScramble(self, s1: str, s2: str) -> bool:
6        if s1 == s2:
7            return True
8        if (s1, s2) in self.memo:
9            return self.memo[(s1, s2)]
10        if sorted(s1) != sorted(s2):
11            return False
12        n = len(s1)
13        for i in range(1, n):
14            if (self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:], s2[i:])) or \
15               (self.isScramble(s1[:i], s2[-i:]) and self.isScramble(s1[i:], s2[:-i])):
16                self.memo[(s1, s2)] = True
17                return True
18        self.memo[(s1, s2)] = False
19        return False

Explanation

This Python solution uses recursion with memoization, checking all possible partition indices and both possible scrambling options. It uses a dictionary for memoization, speeding up repeated queries. Sorting ensures a quick early rejection of incongruent strings.

Dynamic Programming Approach

This approach is based on dynamic programming. We set up a 3D table where table[i][j][k] holds true if s1's substring starting at index i with length k is a scrambled string of s2's substring starting at index j.

Time Complexity: O(N^4), where N is the length of the strings.
Space Complexity: O(N^3), due to the 3D DP table.

C C++Java Python C#JavaScript

1using System;
2
public class Solution {
    public bool IsScramble(string s1, string s2) {
        int n = s1.Length;
        if (s1 == s2) return true;
        char[] sorted1 = s1.ToCharArray();
        Array.Sort(sorted1);
        char[] sorted2 = s2.ToCharArray();
        Array.Sort(sorted2);
        if (!new String(sorted1).Equals(new String(sorted2))) return false;

        bool[,,] dp = new bool[n, n, n + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i, j, 1] = s1[i] == s2[j];
            }
        }

        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++) {
                        if ((dp[i, j, k] && dp[i + k, j + k, len - k]) ||
                            (dp[i, j + len - k, k] && dp[i + k, j, len - k])) {
                            dp[i, j, len] = true;
                            break;
                        }
                    }
                }
            }
        }

        return dp[0, 0, n];
    }
}