Leetcode 87: Scramble String

1. Problem Statement (Simple Explanation)

We define a scramble operation on a string s:

• If |s| == 1: stop.

• If |s| > 1:

1. Split s at some index i into two non-empty substrings: x = s[0..i-1], y = s[i..end].

2. Randomly choose to keep them in order (x + y) or swap them (y + x).

3. Recursively apply the same process to x and y.

Given two strings s1 and s2 of equal length, return true if s2 is a scrambled string of s1 under this definition, otherwise false.

Constraints:

• 1 <= length(s1) <= 30

• s1.length == s2.length

• Both consist of lowercase letters.

2. Examples

Example 1:

Input: s1 = "great", s2 = "rgeat"

One valid scrambling sequence:

• "great" → split "gr" + "eat"

• No swap: "gr" + "eat"

• Recurse: "gr" → "g" + "r" → swap → "rg"

• Recurse: "eat" → "e" + "at" → "e" + "a" + "t" (no swaps)

• Final: "rgeat" → matches s2.

Output: true

Example 2:

Input: s1 = "abcde", s2 = "caebd"

No valid way to recursively split/swap "abcde" to get "caebd".

Output: false

Example 3:

Input: s1 = "a", s2 = "a"

Single character, identical.

Output: true

3. Approach – Top-Down Recursion with Memoization

This is a classic recursive + memoization (DP) problem.

3.1 Key Observations:

1. Lengths must match: if s1.length != s2.length, immediately false.

2. Character multiset must match:

• For any scrambled string, the two strings are permutations of each other.

• If sorted(s1) != sorted(s2), then false (or we can count frequency to avoid sorting).

3. Recursion on splits:

• For substring s1[i1..i1+len-1] and s2[i2..i2+len-1], we try all possible split positions k from 1 to len-1:

• Case 1: No swap at this split:

s1[i1..i1+k-1]  ↔ s2[i2..i2+k-1]

s1[i1+k..i1+len-1] ↔ s2[i2+k..i2+len-1]

• Case 2: Swap at this split:

s1[i1..i1+k-1]  ↔ s2[i2+len-k..i2+len-1]

s1[i1+k..i1+len-1] ↔ s2[i2..i2+len-k-1]

• If for any k, one of these two cases returns true, the pair is scrambled.

4. Subproblem definition:

• isScramble(i1, i2, len) → whether s1.substring(i1, i1+len) is a scramble of s2.substring(i2, i2+len).

5. Memoization:

• Many states repeat due to overlapping subproblems.

• Use a 3D memo or a hash map keyed on (i1, i2, len) to store results:

• -1 = unknown/uncomputed, 0 = false, 1 = true.

Given n <= 30, state space is manageable: O(n³).

3.2 Recursive Algorithm:

Function: dfs(i1, i2, len)

1. If memo[i1][i2][len] is known, return stored value.

2. Take substrings s1[i1..i1+len-1] and s2[i2..i2+len-1]:

• If they are equal, return true (memoize).

3. Check if they have the same char multiset:

• Count frequencies over this substring; if mismatch, memoize false.

4. Try all splits k = 1 .. len-1:

• No swap:

if dfs(i1,       i2,       k) &&

   dfs(i1 + k,   i2 + k,   len - k):

   memo[i1][i2][len] = true; return true

• Swap:

if dfs(i1,       i2 + len - k, k) &&

   dfs(i1 + k,   i2,           len - k):

   memo[i1][i2][len] = true; return true

5. If none succeed, memorize false.

Pseudo-code:

Complexity:

• Number of states: O(n3) (i1, i2, len each ~ n).

• Each state tries up to len-1 splits → worst O(n).

• With pruning via char counts and equality check, practical performance is good for n <= 30.

Worst theoretical: O(n4) but passable with constraints and pruning.

Space:

• Memo table: O(n³)

• Recursion depth: O(n)

We’ll implement the dfs(i1, i2, len) approach with memoization and simple frequency-based pruning.

4. Java code

5. C code

C implementation is more verbose due to 3D memo and indexing; conceptually it is the same as Java/C++:

• Use memo[n][n][n+1] with values -1, 0, 1.

• Store s1, s2 as globals or pass pointers.

• Do the same frequency pruning and recursive splitting.

For LeetCode, C++/Java/Python/JS are more convenient.

6. C++ code

7. Python code

Note: Using sorted() is simple but a bit heavier. For extra performance, you can replace with a frequency count as done in Java/C++.

8. JavaScript code