We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Scramble String

Number: 87

Difficulty: Hard

Paid? No

Companies: Google, Media.net, Amazon, Meta

Problem Description

Given two strings s1 and s2 of equal length, determine if s2 is a scrambled string of s1. A scramble of a string is generated by recursively splitting the string into two non-empty parts and swapping them optionally.

Key Insights

  • Use recursion to try all possible ways to partition the string.
  • Leverage memoization to cache results for string pairs to reduce repeated computations.
  • Before recursing, perform simple checks: if the strings are equal or if their sorted characters do not match (a quick check for mismatches).
  • For each partition, handle two cases: one where the parts are not swapped, and one where they are swapped.

Space and Time Complexity

Time Complexity: Exponential in the worst-case, but memoization helps prune redundant recursions. Space Complexity: O(n^2) due to the memoization storage for all substring pairs.

Solution

We solve this problem using a recursive approach combined with memoization. At each recursive call, we:

  1. Check if the two strings are identical.
  2. Perform a frequency check (by sorting) to ensure both strings contain the same characters.
  3. Try every possible split position. For each split, we check two cases:
    • Without swapping: the first part of s1 corresponds to the first part of s2, and the second parts correspond.
    • With swapping: the first part of s1 corresponds to the last part of s2, and vice versa.
  4. Cache the results for each (s1, s2) pair in a memoization structure (like a hash map) to avoid repeated work. This approach ensures we explore all possibilities while efficiently pruning impossible cases.

Code Solutions

def isScramble(s1: str, s2: str) -> bool:
    # Dictionary to store computed results for string pairs.
    memo = {}

    def rec(a: str, b: str) -> bool:
        # If result already computed, return it.
        if (a, b) in memo:
            return memo[(a, b)]
        # If the strings are equal, they are scramble of each other.
        if a == b:
            memo[(a, b)] = True
            return True
        # Quick check: if sorted characters differ, they cannot be scrambles.
        if sorted(a) != sorted(b):
            memo[(a, b)] = False
            return False
        n = len(a)
        # Try every possible split position.
        for i in range(1, n):
            # Check the non-swapped case.
            if rec(a[:i], b[:i]) and rec(a[i:], b[i:]):
                memo[(a, b)] = True
                return True
            # Check the swapped case.
            if rec(a[:i], b[-i:]) and rec(a[i:], b[:-i]):
                memo[(a, b)] = True
                return True
        memo[(a, b)] = False
        return False

    return rec(s1, s2)

# Example usage:
print(isScramble("great", "rgeat"))  # Expected output: True
← Back to All Questions