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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Scramble String

Difficulty: Hard

Problem Description

Given two strings s1 and s2 of the same length, return true if s2 is a scrambled string of s1, otherwise, return false. A string is considered scrambled if it can be obtained from another string by recursively splitting it into two non-empty substrings and potentially swapping those substrings.

Key Insights

  • The strings must have the same characters in the same frequency to be considered scrambled.
  • Recursive division of the strings allows for multiple combinations that could lead to a match.
  • Memoization can be employed to optimize the recursive checks and avoid redundant calculations.

Space and Time Complexity

Time Complexity: O(n^4) in the worst case due to recursive calls and substring comparisons, but can be optimized with memoization. Space Complexity: O(n^2) for the memoization table to store results of substring comparisons.

Solution

The solution involves a recursive function that checks if two given substrings are scrambled versions of each other. We can divide the strings at every possible index and check both the cases where we swap the substrings and where we do not swap them. Using memoization, we can store results of previously computed substring comparisons to avoid redundant calculations.

Code Solutions

def isScramble(s1: str, s2: str) -> bool:
    if len(s1) != len(s2):
        return False
    if s1 == s2:
        return True
    if sorted(s1) != sorted(s2):  # Check if they have the same characters
        return False
    
    n = len(s1)
    memo = {}
    
    def dfs(x, y, length):
        if (x, y, length) in memo:
            return memo[(x, y, length)]
        
        if s1[x:x + length] == s2[y:y + length]:
            memo[(x, y, length)] = True
            return True
        
        for i in range(1, length):
            # Check without swapping
            if (dfs(x, y, i) and dfs(x + i, y + i, length - i)) or \
               (dfs(x, y + length - i, i) and dfs(x + i, y, length - i)):
                memo[(x, y, length)] = True
                return True
        
        memo[(x, y, length)] = False
        return False
    
    return dfs(0, 0, n)
← Back to All Questions