LeetCode 87: Scramble String Solution in Python Explained

Problem Statement

In LeetCode 87, you’re given two strings s1 and s2 of the same length. A string can be scrambled by splitting it into two non-empty substrings, recursively scrambling them, and optionally swapping their order. Your task is to check if s1 can become s2 through this process. This is distinct from list problems like LeetCode 86: Partition List, focusing instead on string transformations.

Constraints

• String length: 1 <= s1.length, s2.length <= 30
• s1.length == s2.length
• Characters: lowercase English letters

Example

Let’s see some cases:

Copy codeInput: s1 = "great", s2 = "rgeat"
Output: true
Explanation: great -> gr/eat -> rgeat (split, swap gr and eat, scramble).

Copy codeInput: s1 = "abcde", s2 = "caebd"
Output: false
Explanation: No scramble path from abcde to caebd.

Copy codeInput: s1 = "a", s2 = "a"
Output: true
Explanation: Identical single characters.

These examples show we’re checking scramble equivalence.

Understanding the Problem

How do you solve LeetCode 87: Scramble String in Python? Take s1 = "great", s2 = "rgeat". We need to see if great can transform into rgeat by splitting (e.g., "gr" and "eat"), scrambling, and swapping (e.g., "rgeat" = "rg" + "eat"). This isn’t a simple array task like LeetCode 1: Two Sum; it’s about recursive string partitioning. We’ll use: 1. Dynamic Programming with Recursion: O(n⁴) time, O(n³) space—our best pick. 2. Brute Force Recursion: O(2ⁿ) time, O(n) space—a baseline.

Let’s dive into the primary solution.

Solution 1: Dynamic Programming with Recursion Approach (Primary)

Explanation

We use a recursive function with memoization to avoid recomputing subproblems. For each substring pair, check all possible splits, verifying if they match either directly or swapped, using a 3D DP table to store results based on start indices and length. Early checks (length, character frequency) optimize it.

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

• Split at 2: "gr" vs. "rg", "eat" vs. "eat".
• "gr" scrambles to "rg", "eat" matches "eat".
• True.

Step-by-Step Example

Example 1: s1 = "great", s2 = "rgeat"

Goal: Return true.

• Start: isScramble("great", "rgeat"), n = 5.
• Step 1: Length = 5, chars match (a,e,g,r,t).
• Split at 1: "g" vs. "r", "reat" vs. "geat".
• "g" != "r", false.
• Split at 2: "gr" vs. "rg", "eat" vs. "eat".
• "gr" vs. "rg": Split at 1: "g" vs. "r", "r" vs. "g" → false; swap: "gr" vs. "gr" → true.
• "eat" vs. "eat": true.
• True (memoized).
• Stop at first true: dp[0][0][5] = true.
• Finish: Return true.

Example 2: s1 = "abcde", s2 = "caebd"

Goal: Return false.

• Start: n = 5.
• Step 1: Length = 5, chars match (a,b,c,d,e).
• Split at 1: "a" vs. "c", "bcde" vs. "aebd" → false.
• Split at 2: "ab" vs. "ca", "cde" vs. "ebd" → false; swap "ab" vs. "eb" → false.
• Split at 3: "abc" vs. "cae", "de" vs. "bd" → false; swap "abc" vs. "bd" → false.
• Split at 4: "abcd" vs. "caeb", "e" vs. "d" → false.
• Finish: All splits false, return false.

Example 3: s1 = "a", s2 = "a"

Goal: Return true.

• Start: n = 1.
• Step 1: Length = 1, "a" == "a".
• Finish: Return true.

How the Code Works (Dynamic Programming with Recursion) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codefrom functools import lru_cache
from collections import Counter

def isScramble(s1: str, s2: str) -> bool:
    # Line 1: Define recursive function with memoization
    @lru_cache(None)
    def dp(i1: int, i2: int, length: int) -> bool:
        # i1 = start index in s1, i2 = start index in s2, length = substring length
        # @lru_cache caches results based on (i1, i2, length)

        # Line 2: Extract substrings
        str1 = s1[i1:i1 + length]
        str2 = s2[i2:i2 + length]
        # Gets substrings from s1 and s2 (e.g., i1=0, length=5: "great", i2=0: "rgeat")

        # Line 3: Base case - identical strings
        if str1 == str2:
            # If substrings are equal (e.g., "eat" == "eat"), they’re scramble-equivalent
            return True

        # Line 4: Base case - length 1
        if length == 1:
            # If length is 1, strings match if characters are equal (e.g., "a" == "a")
            # Already checked equality, so return False if we’re here
            return False

        # Line 5: Check character frequency for early exit
        if Counter(str1) != Counter(str2):
            # If character counts differ (e.g., "ab" vs. "cd"), they can’t scramble
            # Uses Counter to compare (faster than sorting for small strings)
            return False

        # Line 6: Try all possible splits
        for k in range(1, length):
            # k = split point, from 1 to length-1 (e.g., 1 to 4 for length 5)
            # Tests all ways to divide the string into two non-empty parts

            # Line 7: Case 1 - no swap
            if dp(i1, i2, k) and dp(i1 + k, i2 + k, length - k):
                # Checks if first k chars scramble and remaining length-k chars scramble
                # e.g., "gr" vs. "rg" (k=2) and "eat" vs. "eat" (length-k=3)
                # If both true, this split works without swapping
                return True

            # Line 8: Case 2 - with swap
            if dp(i1, i2 + length - k, k) and dp(i1 + k, i2, length - k):
                # Checks swapped order: first k of s1 vs. last k of s2, and vice versa
                # e.g., "gr" vs. "at" (k=2) and "eat" vs. "rge" (length-k=3)
                # If both true, this split works with swapping
                return True

        # Line 9: No valid split found
        return False
        # If all splits fail, these substrings can’t scramble

    # Line 10: Check initial conditions
    if len(s1) != len(s2):
        # If lengths differ, they can’t scramble (constraint ensures this, but good practice)
        return False

    # Line 11: Call DP function with full strings
    return dp(0, 0, len(s1))
    # Starts recursion with full strings: i1=0, i2=0, length=len(s1)
    # Returns true if s1 can scramble to s2

This detailed breakdown makes the DP logic crystal clear.

Alternative: Brute Force Recursion Approach

Explanation

Recursively split s1 and s2 at all points, checking if substrings match directly or swapped, without memoization. Exponential time due to repeated subproblems.

For "great" vs. "rgeat":

• Split at 2: "gr" vs. "rg", "eat" vs. "eat" → true.

Step-by-Step Example (Alternative)

For "great", "rgeat":

• Split at 2: "gr" vs. "rg" (true), "eat" vs. "eat" (true).
• Finish: True.

How the Code Works (Brute Force)

Copy codedef isScrambleBrute(s1: str, s2: str) -> bool:
    if s1 == s2:
        return True
    if len(s1) != len(s2) or sorted(s1) != sorted(s2):
        return False
    n = len(s1)
    for i in range(1, n):
        if (isScrambleBrute(s1[:i], s2[:i]) and isScrambleBrute(s1[i:], s2[i:])) or \
           (isScrambleBrute(s1[:i], s2[n-i:]) and isScrambleBrute(s1[i:], s2[:n-i])):
            return True
    return False

Complexity

• DP with Recursion:
• Time: O(n⁴) – n³ states, O(n) per state.
• Space: O(n³) – DP cache.
• Brute Force:
• Time: O(2ⁿ) – exponential due to branching.
• Space: O(n) – recursion stack.

Efficiency Notes

DP with Recursion is practical for the constraint (n ≤ 30), while Brute Force is too slow—DP is the LeetCode-preferred approach.

Key Insights

• Memoization: Avoids redundant checks.
• Split Points: Test all divisions.
• Swap Option: Key to scrambling.

Additional Example

For s1 = "abc", s2 = "bca":

• Goal: true.
• DP: Split at 1: "a" vs. "b", swap "a" vs. "a", "bc" vs. "bc" → true.

Edge Cases

• Single Char: "a" vs. "a" → true.
• Different Chars: "a" vs. "b" → false.
• Empty: Not applicable (constraint n ≥ 1).

Both solutions handle these well.

Final Thoughts

LeetCode 87: Scramble String in Python is a mind-bending string challenge. The DP with Recursion solution balances efficiency and clarity, while Brute Force is a learning step. Want more? Try LeetCode 76: Minimum Window Substring for string sliding or LeetCode 86 for list partitioning. Ready to practice? Solve LeetCode 87 on LeetCode with "great" and "rgeat", aiming for true—test your skills now!