Abstract / Summary

Given two strings determine if one can be transformed into the other by recursively splitting and swapping their parts

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 45% (700k+ submissions).

Typical patterns to solve this problem:

• Dynamic Programming
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the classic “scramble string” problem using a recursive depth-first search combined with memoization. The public method isScramble receives two strings and delegates the actual work to an inner helper deeper. The helper explores all possible ways to split the strings and checks both the non-swapped and swapped configurations. Early termination is achieved through direct equality checks and character-frequency comparison, while the @cache decorator eliminates redundant recomputation of identical sub-problems.

Core Logic

Early Equality Check

if a == b:
    return True

When the two substrings are identical, the function returns immediately, avoiding any further recursion. This handles the trivial case where the strings are already in the required order.

Character Frequency Pruning

if sorted(a) != sorted(b):
    return False

By sorting both substrings and comparing the results, the algorithm discards branches where the multiset of characters differs. This prevents unnecessary deeper exploration for impossible matches, such as when one substring contains a character that the other does not.

Recursive Partitioning

for i in range(1, len(a)):
    # no swap
    if deeper(a[:i], b[:i]) and deeper(a[i:], b[i:]):
        return True

    # swap
    swapped = a[i:] + a[:i]
    p = len(a) - i
    if deeper(swapped[:p], b[:p]) and deeper(swapped[p:], b[p:]):
        return True

The loop iterates over every possible split position i. For each position, two scenarios are examined:

• The left part of a aligns with the left part of b and the right parts align correspondingly.
• The left part of a is moved to the end (producing swapped), and the new left part of swapped aligns with the left part of b.

If either scenario yields a pair of recursive calls that both return True, the current call returns True as well, indicating a valid scramble configuration.

Default Failure

return False

If none of the split positions produce a successful match, the function concludes that the substrings cannot be scrambled into each other and returns False.

Edge Cases Handled

The algorithm gracefully handles empty strings because the outer loop never executes when the length is zero, and the early equality check will return True only when both inputs are empty. Single-character strings are also covered: the equality check succeeds if the characters match, otherwise the sorted comparison fails, leading to a False result.

When the two strings contain the same characters but in different orders, the sorted comparison passes, allowing the recursive partitioning to explore all possible rearrangements. The swap logic correctly addresses cases where a valid scramble requires swapping the two halves at some recursion depth, such as transforming "great" into "rgeat".

Performance Optimizations

The most significant optimization is the use of the @cache decorator from the functools module. By memoizing the results of deeper(a, b), the implementation avoids recomputing the same substring pair multiple times, which dramatically reduces the exponential blow-up typical of naïve recursive solutions.

The early equality and sorted checks act as cheap filters that prune large portions of the recursion tree before any deeper calls are made. This reduces the number of cached entries and the overall number of recursive invocations.

The construction of the swapped string (a[i:] + a[:i]) is performed only when the non-swap scenario fails for a particular split, ensuring that the extra concatenation cost is incurred only when necessary.

Together, these techniques keep the algorithm efficient enough to handle moderate-size inputs within reasonable time limits.

Imagine there are two blocks filled with letters. To see if one pile of blocks can turn into the other, the computer plays a matching game. It first looks to see if the letters are the same in both piles, because if they are different, it is impossible for them to match.

The computer then takes a deep breath and looks for a place to cut the pile into two smaller pieces. It tries two different approaches. In the first approach, it keeps the pieces in the same order and checks if the smaller parts match up. If that does not work, it tries a second approach where it swaps the pieces around, putting the back part in front, to see if that creates a match instead.

Whenever the computer finds a way to cut and perhaps flip the piles so that they look identical, it feels happy because it knows the two piles are related. If it tries every possible cut and every possible swap and still nothing matches, then it decides the piles are just too different to be the same. The cache helps the computer remember the answers it already found so it does not have to do the same hard work over and over again.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	Python	C++	Java						TS
	WalkCCC	Python	C++	Java
	leetcode.ca	Python	C++	Java			C#		Go	TS
	LeetcodeHelp	Python	C++	Java
	MemoryLimitExceeded	Python	C++
	Progiez	Python	C++	Java
github	aylei				Rust
	begeekmyfriend							C
	BigEggStudy						C#
	black-shadows	Python
	charles-wangkai			Java
	chenyanzhe		C++
	everthis					JS
	gaosq0604	Python
	Garvit244	Python
	haoel		C++
	JoshCrozier					JS
	keineahnung2345		C++
	lkwq007	Python
	lzl124631x		C++
	qiyuangong	Python
	ruoru				Rust
	suxrobGM						C#
	varunu28			Java
	vthwang			Java
	wisdompeak		C++
	XiaotaoGuo		C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	Python, Python
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
gaosq0604	Python
Garvit244	Python
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
lzl124631x	C++
qiyuangong	Python
ruoru	Rust
suxrobGM	C#
varunu28	Java
vthwang	Java
wisdompeak	C++
XiaotaoGuo	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality