Boolean Parenthesization stretched the state from (i, j) to (i, j, isTrue) because a single number stopped being enough to describe a subproblem. Scrambled String stretches things differently. There are now two strings involved instead of one, and at every partition point there's a genuine choice: keep the two halves in order, or swap them. The skeleton is still the same one from MCM. What changes is what counts as a valid match on each side of the split.
The Problem
Given two strings A and B, determine whether B is a scrambled version of A.
A scrambled string comes from repeatedly splitting a string in two and optionally swapping the two halves, recursively, at every level. Picture A = GREAT as a binary tree, where each split produces two children that can optionally be swapped:
GREAT
/ \
GR EAT
/ \ / \
G R E AT
/ \
A T
At any non-leaf node in this tree, the two children are allowed to swap places. Swapping GR gives RG. Swapping EAT gives ATE. If enough of these swaps happen at the right places, GREAT can be transformed into some other arrangement, and the question is whether B is reachable from A this way.
A split always has to produce two non-empty parts. Splitting GREAT into GREAT and an empty string isn't a valid partition, so index 0 and index n are both off-limits as split points.
Two things are worth noting before going further. Zero swaps is a completely valid scramble. If A and B are identical, that's a scrambled string with nothing actually scrambled, and it should return True. And if A and B have different lengths, B can never be a scramble of A at all, so that's an immediate False before anything else gets checked.
Recognising the MCM Pattern
The core question, "where can this string be split," is the same question MCM has been asking all along.
GREAT can split at:
G | REAT
GR | EAT
GRE | AT
GREA | T
String
|
Can be recursively divided into two parts
|
Try every possible partition
|
Check left and right parts
|
MCM / Interval DP pattern
There's no scalar cost being minimized here the way there was in MCM's multiplication cost or Palindrome Partitioning's cut count. What carries over from MCM isn't the specific thing being optimized, it's the structural template underneath all of these problems: partition, solve the left, solve the right, combine. Scrambled String borrows that template and fills in a completely different combining rule.
What Happens After You Partition
Here's where this problem earns its own identity. Split A at position k, giving A1 = A[0:k] and A2 = A[k:n]. B has to be split to match, but because of the swap rule, there are two different ways B's pieces could correspond to A's pieces.
No swap: A1 should match a same-length piece of B taken from the front, and A2 should match the rest of B.
A1 -> B1 (length k)
A2 -> B2 (length n-k)
Check: solve(A1, B1) and solve(A2, B2)
Swap: A1 should match a same-length piece of B taken from the end, and A2 should match whatever's left at the front of B.
A1 -> B2 (length k)
A2 -> B1 (length n-k)
Check: solve(A1, B2) and solve(A2, B1)
Split at k
|
---------------------
| |
No Swap Swap
A1 -> B1 A1 -> B2
A2 -> B2 A2 -> B1
If either the no-swap combination works or the swap combination works, for any valid k, the whole thing is a match. That's an OR across every partition point, and within each partition point, an AND between the two halves matching. k ranges from 1 to n-1 inclusive, the same non-empty-halves constraint mentioned earlier:
for k in range(1, n):
The Base Cases
Three checks run before any partitioning happens, and they're worth doing in this specific order, since each one is cheaper than the next and can short-circuit the more expensive recursive work below it.
Length mismatch: if len(A) != len(B), return False immediately. Nothing else needs checking.
Exact match: if A == B, return True. Zero swaps is a legitimate scramble, and this also happens to be the natural base case that ends the recursion once a partition has been narrowed down to matching single characters.
Anagram pruning: if sorted(A) != sorted(B), return False. This one is worth sitting with, because it's not obviously necessary the way the first two checks are; it's an optimization built on a real property of the problem. Swapping the two children of a node in the scramble tree rearranges characters, but it can never create or destroy them, and it can never change how many of each character exist. So if A and B don't contain the same multiset of characters, no sequence of swaps, at any level of the tree, could ever turn one into the other. Checking this early prunes off entire branches of recursion that are doomed before a single partition gets tried.
if len(A) != len(B):
return False
if A == B:
return True
if sorted(A) != sorted(B):
return False
The Recursive Solution
class Solution:
def solve(self, A, B):
if len(A) != len(B):
return False
if A == B:
return True
if sorted(A) != sorted(B):
return False
n = len(A)
for k in range(1, n):
# No Swap
left = self.solve(A[:k], B[:k])
right = self.solve(A[k:], B[k:])
if left and right:
return True
# Swap
left = self.solve(A[:k], B[n - k:])
right = self.solve(A[k:], B[:n - k])
if left and right:
return True
return False
def isScramble(self, s1, s2):
return self.solve(s1, s2)
The swapped indexing is the detail most likely to trip you up on a first read, so it's worth spelling out explicitly. A1, the first k characters of A, has length k, so in the swap case it needs to match the last k characters of B, which is B[n-k:]. A2, the remaining n-k characters of A, needs to match whatever's left, the first n-k characters of B, which is B[:n-k]. The lengths on both sides always have to agree; only which end of B they're pulled from changes between the swap and no-swap cases.
Memoizing with a Dictionary
The recursion above re-solves identical (A, B) substring pairs across different partition branches constantly, which is the same overlapping-subproblems signal that justified memoization in every earlier chapter of this series. The most direct way to cache it is keying on the actual substrings themselves.
class Solution:
def solve(self, A, B, memo):
if len(A) != len(B):
return False
if A == B:
return True
if sorted(A) != sorted(B):
return False
key = (A, B)
if key in memo:
return memo[key]
n = len(A)
for k in range(1, n):
# No Swap
left = self.solve(A[:k], B[:k], memo)
right = self.solve(A[k:], B[k:], memo)
if left and right:
memo[key] = True
return True
# Swap
left = self.solve(A[:k], B[n - k:], memo)
right = self.solve(A[k:], B[:n - k], memo)
if left and right:
memo[key] = True
return True
memo[key] = False
return False
def isScramble(self, s1, s2):
memo = {}
return self.solve(s1, s2, memo)
The key is the pair (A, B) itself, the actual substrings, not indices. This works correctly, but it's worth noticing what it's actually storing: two full string objects per cache entry, which is more memory than strictly necessary given that every substring here is fully determined by where it starts and how long it is.
Two Ways to Represent the Same State
Both the dictionary approach and an index-based array approach are tracking the exact same logical subproblem. They just describe the coordinates of that subproblem differently.
Dictionary approach: keys are (A, B), the substrings themselves. The length of each substring is implicit, it's just len(A) and len(B), and the starting position within the original string isn't tracked at all, because the substring itself carries all the information needed.
Array approach: coordinates are T[i][j][length], where i is the starting index into the original A, j is the starting index into the original B, and length is how long the matching substrings are. Nothing gets sliced into a new substring object; the boundaries are computed on demand as A[i : i+length] and B[j : j+length].
Dictionary: key = (A, B) -> substrings carry their own length
Array: key = (i, j, length) -> substrings recomputed from indices
This is the same tradeoff that shows up anywhere a problem can be memoized either by value (the actual substring) or by position (indices into the original string). The array version avoids the overhead of creating and hashing new string objects on every recursive call, at the cost of needing one more dimension, length, that the dictionary version got for free by just measuring the strings it was already holding onto.
The 3D Index-Based Version
class Solution:
def solve(self, A, B, i, j, length, T):
if length == 1:
return A[i] == B[j]
if T[i][j][length] != -1:
return T[i][j][length]
if A[i:i + length] == B[j:j + length]:
T[i][j][length] = 1
return True
if sorted(A[i:i + length]) != sorted(B[j:j + length]):
T[i][j][length] = 0
return False
for k in range(1, length):
# No Swap
left = self.solve(A, B, i, j, k, T)
right = self.solve(A, B, i + k, j + k, length - k, T)
if left and right:
T[i][j][length] = 1
return True
# Swap
left = self.solve(A, B, i, j + length - k, k, T)
right = self.solve(A, B, i + k, j, length - k, T)
if left and right:
T[i][j][length] = 1
return True
T[i][j][length] = 0
return False
def isScramble(self, s1, s2):
n = len(s1)
if n != len(s2):
return False
T = [
[
[-1] * (n + 1)
for _ in range(n)
]
for _ in range(n)
]
return self.solve(s1, s2, 0, 0, n, T)
T uses three sentinel values: -1 for not yet computed, 0 for False, and 1 for True, since a plain boolean can't represent "haven't checked this yet" the way -1 can.
The swap indexing needs the same care here that it needed in the plain recursive version, just expressed through index arithmetic instead of slicing. For a split at k within a range of length, the left partition has length k and the right partition has length length - k. In the swap case, the left partition of A needs to match against a piece of B starting at j + length - k, that offset is what places it at the end of the current B range rather than the start. The right partition of A matches against B starting right at j, the front of the range.
Quick Revision
Scrambled String
|
Recursive partitioning
|
MCM / Interval DP pattern
|
Try k = 1 to n-1
|
+-----------------+
| |
No Swap Swap
| |
A1 -> B1 A1 -> B2
A2 -> B2 A2 -> B1
| |
+------ OR -------+
|
True/False
Base cases, in order:
len(A) != len(B) -> False
A == B -> True
sorted(A) != sorted(B) -> False (anagram pruning)
Memoization:
Dictionary: key = (A, B)
Array: T[i][j][length], sentinels -1/0/1
What You Now Understand
MCM tells you where to partition. It's the scrambling rule specifically, the choice between matching halves in order or swapped, that tells you how the two sides are allowed to correspond once you've split. That's the part genuinely new to this problem: an extra binary decision at every partition point, checked as an OR across two different pairings rather than a single fixed combination the way MCM and Palindrome Partitioning had.
The other genuinely new idea here is the length dimension in the index-based memoization. Boolean Parenthesization needed one extra dimension, isTrue, because a single count wasn't enough information for a subproblem. Scrambled String needs one extra dimension, length, because tracking a substring by its starting position alone isn't sufficient, you also need to know how far it extends, once you stop carrying that information implicitly inside an actual sliced-out string.
Top comments (0)