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.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) |
Aditya Verma
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.
1#include <string.h>
2#include <stdbool.h>
3#include <stdlib.h>
4
5int memo[31][31][31];
6
7bool scrambleUtil(const char* s1, const char* s2, int i1, int i2, int length) {
8 if (strncmp(s1 + i1, s2 + i2, length) == 0) {
9 return true;
10 }
11 if (memo[i1][i2][length] != -1) {
12 return memo[i1][i2][length];
13 }
14 for (int i = 1; i < length; i++) {
15 if ((scrambleUtil(s1, s2, i1, i2, i) && scrambleUtil(s1, s2, i1 + i, i2 + i, length - i)) ||
16 (scrambleUtil(s1, s2, i1, i2 + length - i, i) && scrambleUtil(s1, s2, i1 + i, i2, length - i))) {
17 memo[i1][i2][length] = 1;
18 return true;
19 }
20 }
21 memo[i1][i2][length] = 0;
22 return false;
23}
24
25bool isScramble(char* s1, char* s2) {
26 int n = strlen(s1);
27 if (n != strlen(s2)) {
28 return false;
29 }
30 memset(memo, -1, sizeof(memo));
31 return scrambleUtil(s1, s2, 0, 0, n);
32}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.
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.
1var isScramble
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Scramble String is considered a classic hard dynamic programming problem and can appear in advanced interview rounds. It tests recursion, DP optimization, and understanding of substring partitioning strategies.
The optimal approach uses recursion with memoization or a bottom-up dynamic programming solution. By storing results for substring comparisons, it avoids redundant computations and significantly improves efficiency over naive recursion.
The difficulty comes from the large number of possible substring partitions and swap combinations. Efficiently pruning repeated computations using memoization or DP is essential to make the solution feasible.
Dynamic programming tables or hash maps for memoization work best. They store intermediate results for substring pairs, allowing the algorithm to reuse previously computed states efficiently.
The JavaScript solution involves a three-dimensional array to manage the possible scrambling transitions between the strings. The approach includes an initial check for equal character contents using sorting, and it systematically builds potential scrambles from each substring length.