We can scramble a string s to get a string t using the following algorithm:
s, divide it to x and y where s = x + y.s may become s = x + y or s = y + x.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.length1 <= s1.length <= 30s1 and s2 consist of lowercase English letters.Problem Overview: You are given two strings of equal length. The task is to determine whether one string can be transformed into the other by repeatedly splitting the string into two non-empty parts and optionally swapping those parts. The structure created by these recursive splits defines whether the strings are valid scrambles of each other.
Approach 1: Recursive Approach with Memoization (Time: O(n^4), Space: O(n^3))
This approach directly models the recursive definition of a scramble string. For every substring pair s1[i...j] and s2[i...j], try splitting at every possible index k. Two cases are checked: no swap (left with left and right with right) and swap (left with right and right with left). A memoization map caches results for substring pairs so repeated states are not recomputed. The recursion explores at most O(n^4) states because each substring pair can try up to n partitions, while memoization reduces exponential branching. This method is intuitive and closely follows the recursive structure of the problem, making it a strong baseline when working with string transformations.
Before recursing, you typically check whether both substrings contain the same character frequencies. If they differ, the branch can be pruned immediately. That small optimization significantly cuts the search space.
Approach 2: Dynamic Programming Approach (Time: O(n^4), Space: O(n^3))
The dynamic programming version removes recursion by building results bottom-up. Define dp[len][i][j] as whether the substring of length len starting at i in s1 is a scramble of the substring starting at j in s2. Base cases occur when len = 1, where characters must match. For longer substrings, iterate over every possible split position k and check the same two scenarios used in recursion: no swap and swapped partitions.
This DP table has three dimensions (length and two start indices). For each state you iterate over all split points, producing O(n^4) time complexity with O(n^3) space. The approach is deterministic and avoids recursion stack overhead, which some interviewers prefer when evaluating mastery of dynamic programming. It is also easier to reason about overlapping subproblems compared to raw recursion.
Recommended for interviews: Start by explaining the recursive structure of the scramble definition, then implement the memoized recursion. It shows clear reasoning about overlapping subproblems and pruning. If the interviewer pushes further, describing the bottom-up DP version demonstrates deeper understanding of DP state design and transition logic.
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.
This solution uses a recursive method with memoization to solve the scramble string problem. The base condition checks if the two given substrings are equal. If the memoization array has previously computed the solution for the given problem, it returns that result, which avoids re-computation. The recursive call considers both swapping and not swapping the substrings when partitioning.
Time Complexity: O(N^4), where N is the length of the strings.
Space Complexity: O(N^3), used by the memoization array.
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.
In this C solution, we use a 3D boolean DP array dp with indices [i][j][k] indicating whether a substring starting at index i in s1 and a substring starting at index j in s2 of length k can be scrambles of each other. We fill this array iteratively, considering the divisions of the k-length substring into parts.
Time Complexity: O(N^4), where N is the length of the strings.
Space Complexity: O(N^3), due to the 3D DP table.
We design a function dfs(i, j, k), which means whether the substring starting from i with length k in s_1 can be converted into the substring starting from j with length k in s_2. If it can be converted, return true, otherwise return false. The answer is dfs(0, 0, n), where n is the length of the string.
The calculation method of function dfs(i, j, k) is as follows:
k=1, then we only need to judge whether s_1[i] and s_2[j] are equal. If they are equal, return true, otherwise return false;k \gt 1, we enumerate the length of the split part h, then there are two cases: if the two substrings of the split are not swapped, then it is dfs(i, j, h) \land dfs(i+h, j+h, k-h); if the two substrings of the split are swapped, then it is dfs(i, j+k-h, h) \land dfs(i+h, j, k-h). If one of the two cases is true, then dfs(i, j, k) is true, return true, otherwise return false.Finally, we return dfs(0, 0, n).
In order to avoid repeated calculation, we can use memory search.
The time complexity is O(n^4), and the space complexity is O(n^3). Where n is the length of the string.
We define f[i][j][k] as whether the substring of length k starting from i of string s_1 can be transformed into the substring of length k starting from j of string s_2. Then the answer is f[0][0][n], where n is the length of the string.
For substring of length 1, if s_1[i] = s_2[j], then f[i][j][1] = true, otherwise f[i][j][1] = false.
Next, we enumerate the length k of the substring from small to large, and enumerate i from 0, and enumerate j from 0. If f[i][j][h] \land f[i + h][j + h][k - h] or f[i][j + k - h][h] \land f[i + h][j][k - h] is true, then f[i][j][k] is also true.
Finally, we return f[0][0][n].
The time complexity is O(n^4), and the space complexity is O(n^3). Where n is the length of the string.
| Approach | Complexity |
|---|---|
| Recursive Approach with Memoization | Time Complexity: O(N^4), where N is the length of the strings. |
| Dynamic Programming Approach | Time Complexity: O(N^4), where N is the length of the strings. |
| Memorized Search | — |
| Dynamic Programming (Interval DP) | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive with Memoization | O(n^4) | O(n^3) | Best for explaining the recursive definition of scramble strings and quickly implementing a top-down solution. |
| Dynamic Programming (Bottom-Up) | O(n^4) | O(n^3) | Preferred when avoiding recursion or when demonstrating strong DP state modeling in interviews. |
Scramble string | Dynamic Programming | MCM | Leetcode #87 • Techdose • 29,355 views views
Watch 9 more video solutions →Practice Scramble String with our built-in code editor and test cases.
Practice on FleetCode