LeetCode Problem 87

Difficulty: 🔴 Hard
Topics: String, Dynamic Programming

Solution

LeetCode 87 - Scramble String

Problem Understanding

This problem asks us to determine whether one string can be transformed into another using a specific recursive scrambling process.

We are given two strings, s1 and s2, and they are guaranteed to have the same length. The scrambling process works recursively. At every step, we may split a string into two non-empty parts, optionally swap those parts, and then recursively apply the same process to both halves.

The key challenge is that scrambling does not simply reorder characters arbitrarily. The transformation must arise from repeated binary splits and optional swaps. This means some strings with identical characters are still not valid scrambles.

For example, "great" can become "rgeat" through recursive partitioning and selective swapping. However, "abcde" cannot become "caebd" even though both contain exactly the same letters.

The input consists of:

• s1, the original string
• s2, the target string

The expected output is:

• true if s2 can be generated from s1 through recursive scrambling
• false otherwise

The constraints are important:

• 1 <= s1.length <= 30
• Strings contain only lowercase English letters.
• s1.length == s2.length

The relatively small maximum length of 30 strongly suggests that an exponential brute-force search may be possible conceptually, but must be optimized heavily to pass within time limits. Since recursive splitting creates many overlapping subproblems, dynamic programming or memoization becomes a strong candidate.

There are several important edge cases to consider upfront.

If both strings are identical, the answer is immediately true, since no scrambling is required.

If the strings contain different character frequencies, the answer must be false. Scrambling only rearranges structure, it never changes characters.

Single-character strings are another important case. If both characters match, the answer is true; otherwise, it is false.

A naive implementation can also fail on repeated characters such as "aabb" and "abab", where many recursive partitions appear similar. Memoization is necessary to avoid recomputing identical subproblems repeatedly.

Approaches

Brute Force Recursive Search

The most direct approach is to simulate the scrambling process recursively.

At every recursive call, we try every possible split position. Suppose the current substring has length n. We can split it at every index from 1 to n - 1.

For each split, we test two possibilities:

1. No swap:

• Left part of s1 matches left part of s2
• Right part of s1 matches right part of s2

2. Swap:

• Left part of s1 matches right part of s2
• Right part of s1 matches left part of s2

If any partition works recursively, the strings are valid scrambles.

This approach is correct because it explores every possible recursive split and swap decision exactly as defined by the scrambling rules.

Unfortunately, it is extremely slow. The same substring combinations are recomputed repeatedly, producing massive overlap. Even for moderate string lengths, the number of recursive states grows explosively.

Optimal Approach, Dynamic Programming with Memoization

The key insight is that recursive subproblems repeat frequently.

Suppose we already determined whether "great" can scramble into "rgeat". If this exact comparison appears again deeper in recursion, recomputing it is wasteful.

We can memoize results using a cache keyed by (substring1, substring2).

Another major optimization is character frequency pruning.

Before trying recursive partitions, we compare character counts. If two substrings do not contain the same multiset of letters, scrambling is impossible and we can immediately return false.

This pruning dramatically reduces the search space.

The resulting algorithm becomes a top-down dynamic programming solution:

• Recursively test all split positions.
• Cache results for repeated states.
• Prune impossible branches using character frequency checks.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential, roughly O(2^n * n!)	O(n) recursion	Explores all split/swap possibilities repeatedly
Optimal	O(n⁴)	O(n³)	Memoization avoids repeated work, pruning improves efficiency

Algorithm Walkthrough

Optimal Algorithm, Memoized DFS

1. Check if the strings are already equal

If the two current substrings are identical, immediately return true.

This is important because identical substrings require no scrambling and allow recursion to terminate quickly. 2. Check character frequencies

Before exploring recursive splits, verify both substrings contain the same characters.

Since scrambling never changes character counts, mismatched frequencies guarantee failure.

For example:

• "abc" and "abd" → impossible
• "great" and "rgeat" → still possible

3. Check memoized results

Use a cache to store previously computed states.

The key is (substring1, substring2).

If we have already solved this subproblem, return the cached answer immediately. 4. Try every split position

For a substring of length n, try splitting at indices:

1 through n - 1

For each split index i, test both valid scramble possibilities. 5. Case 1, No swap

Split both strings at the same index:

s1 = left1 + right1
s2 = left2 + right2

Recursively check:

left1 matches left2
AND
right1 matches right2

6. Case 2, Swap

Split s2 differently:

s1 = left1 + right1
s2 = right2 + left2

Recursively check:

left1 matches right2
AND
right1 matches left2

7. Store result in memoization table

If either case succeeds, cache true.

Otherwise, after testing all splits, cache false. 8. Return final answer

The recursion eventually resolves whether s2 is a valid scramble of s1.

Why it works

The algorithm is correct because it exactly mirrors the recursive definition of scrambling.

Every valid scramble must arise from some split position and either preserve or swap child order. By testing every split and both structural possibilities, we exhaustively explore all legal scramble transformations.

Memoization does not change correctness. It only prevents recomputing identical subproblems. Character frequency pruning is also safe because scrambling preserves character counts, meaning any mismatch makes success impossible.

Python Solution

from functools import lru_cache
from collections import Counter

class Solution:
    def isScramble(self, s1: str, s2: str) -> bool:
        if len(s1) != len(s2):
            return False

        @lru_cache(maxsize=None)
        def dfs(str1: str, str2: str) -> bool:
            # Exact match
            if str1 == str2:
                return True

            # Character frequency pruning
            if Counter(str1) != Counter(str2):
                return False

            n = len(str1)

            # Try every split point
            for split_index in range(1, n):
                # Case 1: No swap
                no_swap = (
                    dfs(str1[:split_index], str2[:split_index])
                    and dfs(str1[split_index:], str2[split_index:])
                )

                if no_swap:
                    return True

                # Case 2: Swap
                swap = (
                    dfs(str1[:split_index], str2[n - split_index:])
                    and dfs(str1[split_index:], str2[:n - split_index])
                )

                if swap:
                    return True

            return False

        return dfs(s1, s2)

The implementation starts with a length check for safety, although the problem guarantees equal lengths.

The recursive helper function dfs() represents the core dynamic programming state. It answers the question:

Can str2 be formed by scrambling str1?

The @lru_cache decorator memoizes results automatically. This prevents recomputation of repeated substring pairs.

The equality check comes first because exact matches are trivially valid scrambles.

Next comes the character frequency pruning step using Counter. This eliminates impossible branches early.

The loop tries every possible split index. For each split, we test both valid recursive structures:

• keeping order unchanged
• swapping the left and right partitions

If either recursive branch succeeds, we immediately return True.

If no split works, the substrings cannot be scrambled into each other, so we return False.

Go Solution

func isScramble(s1 string, s2 string) bool {
	if len(s1) != len(s2) {
		return false
	}

	memo := make(map[string]bool)
	visited := make(map[string]bool)

	var dfs func(string, string) bool

	dfs = func(str1 string, str2 string) bool {
		key := str1 + "#" + str2

		if visited[key] {
			return memo[key]
		}

		visited[key] = true

		// Exact match
		if str1 == str2 {
			memo[key] = true
			return true
		}

		// Character frequency pruning
		count := [26]int{}

		for i := 0; i < len(str1); i++ {
			count[str1[i]-'a']++
			count[str2[i]-'a']--
		}

		for _, value := range count {
			if value != 0 {
				memo[key] = false
				return false
			}
		}

		n := len(str1)

		// Try every split
		for splitIndex := 1; splitIndex < n; splitIndex++ {

			// Case 1: No swap
			if dfs(str1[:splitIndex], str2[:splitIndex]) &&
				dfs(str1[splitIndex:], str2[splitIndex:]) {
				memo[key] = true
				return true
			}

			// Case 2: Swap
			if dfs(str1[:splitIndex], str2[n-splitIndex:]) &&
				dfs(str1[splitIndex:], str2[:n-splitIndex]) {
				memo[key] = true
				return true
			}
		}

		memo[key] = false
		return false
	}

	return dfs(s1, s2)
}

The Go implementation follows the same recursive structure as Python but uses maps for memoization.

Since Go does not have a built-in memoization decorator like lru_cache, we manually manage caching with two maps:

• memo stores computed results
• visited tracks whether a state has already been evaluated

Instead of Counter, Go uses a fixed-size frequency array of length 26, which is more efficient for lowercase English letters.

String slicing in Go works efficiently for substrings, making recursion straightforward.

Integer overflow is not a concern because all values remain very small within the constraints.

Worked Examples

Example 1

s1 = "great"
s2 = "rgeat"

We begin:

Step	str1	str2	Result
1	great	rgeat	not equal

Character counts match.

Try split at 1:

g | reat
r | geat

No swap fails:

g != r

Swap case:

g matches g
reat matches rea?

Still fails.

Try split at 2:

gr | eat
rg | eat

No swap:

Recursive check:

gr -> rg
eat -> eat

eat == eat → true

Now solve:

gr -> rg

Split at 1:

g | r
r | g

Swap succeeds:

g == g
r == r

Final result:

true

Example 2

s1 = "abcde"
s2 = "caebd"

Character counts match.

Try every split:

Split	No Swap	Swap
1	fails	fails
2	fails	fails
3	fails	fails
4	fails	fails

No valid recursive partition exists.

Result:

false

Example 3

s1 = "a"
s2 = "a"

Immediate equality:

"a" == "a"

Return:

true

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n⁴)	O(n³) states, each tries O(n) split points
Space	O(n³)	Memoization cache plus recursion stack

The complexity comes from counting unique states.

Each state corresponds to a pair of substrings. There are approximately O(n³) unique substring combinations because we choose a starting position and length.

For every state, we try all split points, which adds another factor of O(n).

This gives total time complexity:

O(n⁴)

The memoization table stores results for substring pairs, requiring:

O(n³)

space.

Test Cases

solution = Solution()

# Provided examples
assert solution.isScramble("great", "rgeat") is True  # standard valid scramble
assert solution.isScramble("abcde", "caebd") is False  # impossible scramble
assert solution.isScramble("a", "a") is True  # single character

# Exact matches
assert solution.isScramble("abc", "abc") is True  # identical strings

# Simple swaps
assert solution.isScramble("ab", "ba") is True  # direct swap

# Different characters
assert solution.isScramble("abc", "abd") is False  # character mismatch

# Repeated characters
assert solution.isScramble("aabb", "abab") is True  # repeated letters

# Complex valid scramble
assert solution.isScramble("great", "rgtae") is True  # deeper recursion

# Same characters, invalid structure
assert solution.isScramble("abcde", "eadcb") is False  # permutation but invalid

# Boundary case
assert solution.isScramble("z", "z") is True  # smallest input

# Larger valid scramble
assert solution.isScramble("abcdefghijklmnop", "efghijklmndopabc") is False  # stress test

Test Summary

Test	Why
"great", "rgeat"	Standard valid scramble
"abcde", "caebd"	Standard invalid example
"a", "a"	Minimum input size
"abc", "abc"	Exact equality shortcut
"ab", "ba"	Single swap
"abc", "abd"	Frequency mismatch pruning
"aabb", "abab"	Repeated character handling
"great", "rgtae"	Deep recursive scramble
"abcde", "eadcb"	Same letters but invalid structure
"z", "z"	Smallest boundary case
Long string case	Stress testing recursion and memoization

Edge Cases

Single Character Strings

The smallest valid input length is 1.

For example:

s1 = "a"
s2 = "a"

A buggy implementation might still attempt recursive splitting, which would fail because no split exists. Our implementation avoids this by checking equality immediately. If the strings match, we return true without recursion.

Same Characters but Invalid Scramble Structure

Two strings having identical character counts does not guarantee success.

Example:

s1 = "abcde"
s2 = "caebd"

A naive solution based only on sorting or frequency comparison would incorrectly return true.

Our recursive split checking ensures the transformation follows valid scrambling rules, not just character rearrangement.

Repeated Characters

Repeated characters can produce many duplicate recursive states.

Example:

s1 = "aabb"
s2 = "abab"

Without memoization, recursion may recompute the same substring relationships repeatedly, causing severe performance issues.

The memoization cache ensures each substring pair is solved once, preventing exponential blowup.

Identical Strings

Sometimes no scrambling is required.

Example:

s1 = "great"
s2 = "great"

Without an equality shortcut, the algorithm would unnecessarily explore every split recursively.

Our implementation immediately returns true when substrings are equal, greatly improving efficiency.