Scramble string | Dynamic Programming | MCM | Leetcode #87
Scramble String - Video Solution
Watch 10 video solutions for Scramble String, a hard level problem involving String, Dynamic Programming. This walkthrough by Techdose has 29,718 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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 toxandywheres = x + y. - Randomly decide to swap the two substrings or to keep them in the same order. i.e., after this step,
smay becomes = x + yors = y + x. - Apply step 1 recursively on each of the two substrings
xandy.
- Split the string into two non-empty substrings at a random index, i.e., if the string is
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 <= 30s1ands2consist of lowercase English letters.
Approach Overview
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.
Complexity Analysis
| 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. |