Problem Statement in English

You’re given two strings s1 and s2 of the same length. We say that s2 is a scrambled string of s1 if we can transform s1 into s2 using a series of recursive operations.

A recursive operation is governed by the following rules:

  1. If the string is empty or has only one character, it is considered a scrambled string of itself.
  2. If the string has more than one character, we can split it into two non-empty substrings at any index i (1 <= i < length of the string). This results in two substrings: s1[0:i] and s1[i:].
  3. The strings can either be recombined in the same order or swapped. That is, we can form two new strings: s1[0:i] + s1[i:] or s1[i:] + s1[0:i].
  4. We can then recursively apply the same operation to each of the two substrings.

Return true if s2 is a scrambled string of s1, otherwise return false.

Approach

There’s no smart way to do this. You just have to simulate the process of scrambling and check if s2 can be obtained from s1. The recursive approach is straightforward, but we can optimize it using memoization to avoid redundant calculations.

For each index in the string, we can split s1 into two parts and check both possible combinations (with and without swapping) to see if they can form s2. If any combination works, we return true. If none work, we return false.

We can recursively check all possible splits and combinations, and use memoization to store results of previously computed substrings to improve efficiency.

The reason there are no loops is because in each step the size of the string is reduced, and we are only checking the two possible combinations for each split.

And we’re done!

Solution in Python


class Solution:
    @cache
    def isScramble(self, s1: str, s2: str) -> bool:
        # Base Cases
        if s1 == s2:
            return True
        if len(s1) != len(s2):
            return False

        # Optimization: Early exit if character counts don't match
        if sorted(s1) != sorted(s2):
            return False

        n = len(s1)
        for i in range(1, n):
            # Case 1: Without swapping subtrees
            if self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:], s2[i:]):
                return True

            # Case 2: With swapping subtrees
            if self.isScramble(s1[:i], s2[n - i:]) and self.isScramble(s1[i:], s2[:n - i]):
                return True

        return False

Complexity

  • Time: $O(n^5)$
    This is because there are $2$ strings, each with $n - k + 1$ substrings. Further, $k$ ranges from $1$ to $n - 1$. Upon squaring, we get $n^3$ states.

    In each state we use a nested loop in order to slice it and sort the substrings. Here the nested loop dominates the time complexity.

    Thus the overall time complexity is $O(n^5)$.

  • Space: $O(n^4)$
    We established that there are $n^3$ states. Each state may have upto $n$ characters, thus giving us a space complexity of $O(n^4)$.

Mistakes I Made

I dismissed dynamic programming because I thought that there was no way to get past the cyclical nature of the problem. I also bungled up the time and space complexity analysis.

And we are done.