Scramble String
This problem can be solved using dynamic programming with a threedimensional array to store the states. Here’s a concise explanation followed by the code:
Base Case: If the two strings are equal, return
True
. If they are not anagrams, returnFalse
.Recursive Case: Loop through the possible partition indices
i
and check if the substrings are scrambled in either possible ordering (i.e., with or without swapping).
Here’s the code:


 The
dp
array stores whether substrings ofs1
ands2
of lengthl
, starting ati
andj
, respectively, are scrambled.  The first two loops iterate through possible lengths and starting indices of the substrings.
 The last loop (over
k
) checks the two ways of partitioning the substrings and whether they can be scrambled.  The final result is stored in
dp[n][0][0]
.
The time complexity of this solution is (O(n^4)), and the space complexity is (O(n^3)).
Identifying Problem Isomorphism
“Scramble String” can be mapped to “Interleaving String”.
In “Scramble String”, we are given a string s1 and we need to determine if a given string s2 is a scrambled form of s1. We can scramble a string s by choosing any nonnegative length substring of s, swapping any two characters at least once, and performing the operation as many times as necessary.
In “Interleaving String”, we are given three strings s1, s2, and s3. We need to determine whether s3 is formed by an interleaving of s1 and s2. Interleaving means that letters in s3 should preserve the order of letters in s1 and s2 while allowing for interleaving of letters.
Both involve operations on strings and the preservation of order of characters to some extent, which is why they can be mapped to each other. However, “Interleaving String” is a simpler problem as it does not involve the swapping operation of the “Scramble String” problem. Thus, the concepts learned in solving “Interleaving String” could be a good stepping stone before tackling “Scramble String”.
10 Prerequisite LeetCode Problems
“Scramble String” is a string manipulation problem that involves recursion and dynamic programming. Here are 10 problems to build up to solving the “Scramble String” problem:
“Reverse String” (LeetCode Problem #344): This problem introduces the basics of string manipulation.
“Reverse Words in a String” (LeetCode Problem #151): This problem introduces string manipulation on a word level.
“Valid Anagram” (LeetCode Problem #242): This problem involves analyzing the frequency of characters in strings.
“Longest Palindromic Substring” (LeetCode Problem #5): This problem introduces dynamic programming with string manipulation.
“Word Break” (LeetCode Problem #139): This problem introduces the concept of recursively breaking down a string into valid components.
“Edit Distance” (LeetCode Problem #72): This problem helps you practice string manipulation and dynamic programming.
“Longest Common Subsequence” (LeetCode Problem #1143): This problem gives practice on dynamic programming involving two strings, which will help for “Scramble String”.
“Unique Binary Search Trees” (LeetCode Problem #96): This problem provides an understanding of tree structures, which can help in understanding the structure of scrambled strings.
“Partition Equal Subset Sum” (LeetCode Problem #416): This problem gives you practice on dynamic programming related to partitions, similar to how you partition a string in “Scramble String”.
“Palindrome Partitioning II” (LeetCode Problem #132): This problem involves partitioning a string and using dynamic programming, both of which are useful for “Scramble String”.


Problem Classification
Scramble String  This problem requires determining if a string is a scrambled version of another string. It involves understanding the transformations that can be performed on strings, thus falling under String Transformation Analysis.
Scramble String  This problem is about determining if a text is a scrambled version of another text. It’s about understanding how texts can be changed and manipulated, thus Text Change Analysis.
Language Agnostic Coding Drills
String Manipulation: Understanding how to manipulate strings is a fundamental programming skill. This includes accessing individual characters, slicing or substring operations, and concatenation.
Drill: Write a function that accepts a string and an index, and returns a new string that is a combination of all characters before the index and all characters after the index.
Character to Integer Mapping: In this problem, we map characters to integers using ASCII values, this involves understanding how character encoding works and how to use it.
Drill: Write a function that accepts a character and returns its ASCII value. Then write a function that accepts an ASCII value and returns the corresponding character.
Recursion: Recursion is a method of solving problems where the solution depends on solutions to smaller instances of the same problem.
Drill: Implement the Fibonacci sequence using recursion. The Fibonacci sequence is a series of numbers where a number is the addition of the last two numbers, starting with 0 and 1.
Caching/Memoization: Caching or memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and reusing them when the same inputs occur again.
Drill: Write a recursive function to compute the factorial of a number. Add memoization to this function to optimize it for inputs that have already been computed.
Array Manipulation: This includes understanding how to iterate over an array, how to access elements, how to modify elements, and understanding the time complexity of these operations.
Drill: Implement a function that accepts an array and a number ’n’, and modifies the array such that all elements are multiplied by ’n'.
After mastering these drills, one can combine them to solve the problem of determining if a string is a scrambled form of another string, as presented in the question.
Targeted Drills in Python
Here’s how we can breakdown the problem and develop the solution stepbystep:
 Problem Understanding and Approach
The problem is to determine if a string s2
is a scrambled form of string s1
. A scrambled string is a string that can be made by cutting a string into two nonempty substrings and swapping them, then doing the same (cutting and swapping) recursively on each of the two substrings.
To solve this, we need to:
 Compare the characters and their frequency in both strings.
 Check for all possible partitions in the string, and recursively check if the partitions can be formed from the other string.
 Coding Drills
Basic String Manipulation
 Python:
s1 = "abc"; s2 = s1[:2] + s1[2:]
 Java:
String s1 = "abc"; String s2 = s1.substring(0, 2) + s1.substring(2);
 Python:
Using ASCII value to index array
 Python:
array = [0]*26; array[ord('b')  ord('a')] += 1
 Java:
int[] array = new int[26]; array['b'  'a']++;
 Python:
Recursion
 Python:
1 2 3 4 5
def recur(n): if n <= 1: return n else: return recur(n1) + recur(n2)
 Java:
1 2 3 4 5 6
int recur(int n) { if (n <= 1) return n; else return recur(n1) + recur(n2); }
 Python:
Using Hash Map to Cache Results
 Python:
1 2 3 4
cache = {} cache["test"] = True if "test" in cache: return cache["test"]
 Java:
1 2 3 4 5
Map<String, Boolean> cache = new HashMap<>(); cache.put("test", true); if (cache.containsKey("test")) { return cache.get("test"); }
 Python:
After understanding and practicing the abovementioned fundamental coding drills, the final step is to combine these skills to form the final solution. Understanding how recursion works is particularly important in this problem as we are essentially exploring all possible ways to partition the two strings and recursively checking each partition. We also use a hash map to remember the results of the previous computations, thereby reducing the time complexity of the solution. This technique is often referred to as memoization in dynamic programming.