Scramble String - Leetcode Solution

The Scramble String problem on LeetCode is a dynamic programming problem that asks us to determine if two given strings are scrambled versions of each other.

To solve this problem, we'll need to use dynamic programming to build up a memo table that stores the solutions for smaller subproblems. We'll start with the base case of comparing two single-character strings. If the characters match, we return true. Otherwise, we return false.

Then, we'll use a nested loop to iterate over all possible splits of the original strings into two substrings. For each split, we'll recursively check if the two substrings are scrambled versions of each other. We'll also check the reverse split to handle the case of the second string being the scrambled version of the first.

If any of the splits result in a match, we can return true. Otherwise, we return false.

Here's the step-by-step solution in Python:

def isScramble(s1: str, s2: str) -> bool:
    # Base case: single characters
    if s1 == s2:
        return True
    
    # Base case: different lengths or different character sets
    if len(s1) != len(s2) or sorted(s1) != sorted(s2):
        return False
    
    # Memo table to store solutions for subproblems
    memo = {}
    
    # Recursive function to check if two substrings are scrambled versions
    def checkScramble(left1, right1, left2, right2):
        # Check memo table first
        if (left1, right1, left2, right2) in memo:
            return memo[(left1, right1, left2, right2)]
        
        # Base case: single characters
        if left1 == right1:
            return s1[left1] == s2[left2]
        
        # Check if substrings are anagrams (optimization)
        if sorted(s1[left1:right1+1]) != sorted(s2[left2:right2+1]):
            return False
        
        # Try all possible splits
        for i in range(left1, right1):
            if (checkScramble(left1, i, left2, left2+(i-left1)) 
                    and checkScramble(i+1, right1, left2+(i-left1)+1, right2)):
                memo[(left1, right1, left2, right2)] = True
                return True
            
            # Try reverse split as well
            if (checkScramble(left1, i, right2-(i-left1), right2) 
                    and checkScramble(i+1, right1, left2, right2-(i-left1)-1)):
                memo[(left1, right1, left2, right2)] = True
                return True
        
        # Store result in memo table and return false
        memo[(left1, right1, left2, right2)] = False
        return False
    
    # Start recursive calls from the entire strings
    return checkScramble(0, len(s1)-1, 0, len(s2)-1)

This solution has a time complexity of O(n^4) due to the nested loops and memo table lookups, but it only uses O(n^3) space for the memo table. With some additional optimizations, such as checking for anagrams and avoiding recursive calls with identical substrings, we can reduce the time complexity to O(n^3).

1