Code Implementation

class Solution:
    def isScramble(self, s1: str, s2: str) -> bool:
        from functools import lru_cache

        @lru_cache(maxsize=None)
        def dfs(a, b):
            if a == b:
                return True
            if sorted(a) != sorted(b):
                return False
            n = len(a)
            for i in range(1, n):
                # Without swap
                if dfs(a[:i], b[:i]) and dfs(a[i:], b[i:]):
                    return True
                # With swap
                if dfs(a[:i], b[-i:]) and dfs(a[i:], b[:-i]):
                    return True
            return False

        return dfs(s1, s2)
      

class Solution {
public:
    unordered_map<string, bool> memo;
    
    bool isScramble(string s1, string s2) {
        string key = s1 + " " + s2;
        if (memo.count(key)) return memo[key];
        if (s1 == s2) return memo[key] = true;
        string t1 = s1, t2 = s2;
        sort(t1.begin(), t1.end());
        sort(t2.begin(), t2.end());
        if (t1 != t2) return memo[key] = false;
        int n = s1.size();
        for (int i = 1; i < n; ++i) {
            // No swap
            if (isScramble(s1.substr(0, i), s2.substr(0, i)) &&
                isScramble(s1.substr(i), s2.substr(i)))
                return memo[key] = true;
            // Swap
            if (isScramble(s1.substr(0, i), s2.substr(n-i)) &&
                isScramble(s1.substr(i), s2.substr(0, n-i)))
                return memo[key] = true;
        }
        return memo[key] = false;
    }
};
      

import java.util.*;

class Solution {
    Map<String, Boolean> memo = new HashMap<>();

    public boolean isScramble(String s1, String s2) {
        String key = s1 + " " + s2;
        if (memo.containsKey(key)) return memo.get(key);
        if (s1.equals(s2)) {
            memo.put(key, true);
            return true;
        }
        char[] arr1 = s1.toCharArray();
        char[] arr2 = s2.toCharArray();
        Arrays.sort(arr1);
        Arrays.sort(arr2);
        if (!Arrays.equals(arr1, arr2)) {
            memo.put(key, false);
            return false;
        }
        int n = s1.length();
        for (int i = 1; i < n; i++) {
            // No swap
            if (isScramble(s1.substring(0, i), s2.substring(0, i)) &&
                isScramble(s1.substring(i), s2.substring(i))) {
                memo.put(key, true);
                return true;
            }
            // Swap
            if (isScramble(s1.substring(0, i), s2.substring(n-i)) &&
                isScramble(s1.substring(i), s2.substring(0, n-i))) {
                memo.put(key, true);
                return true;
            }
        }
        memo.put(key, false);
        return false;
    }
}
      

var isScramble = function(s1, s2) {
    const memo = new Map();

    function dfs(a, b) {
        const key = a + "#" + b;
        if (memo.has(key)) return memo.get(key);
        if (a === b) {
            memo.set(key, true);
            return true;
        }
        if ([...a].sort().join('') !== [...b].sort().join('')) {
            memo.set(key, false);
            return false;
        }
        const n = a.length;
        for (let i = 1; i < n; i++) {
            // No swap
            if (dfs(a.slice(0, i), b.slice(0, i)) &&
                dfs(a.slice(i), b.slice(i))) {
                memo.set(key, true);
                return true;
            }
            // Swap
            if (dfs(a.slice(0, i), b.slice(n-i)) &&
                dfs(a.slice(i), b.slice(0, n-i))) {
                memo.set(key, true);
                return true;
            }
        }
        memo.set(key, false);
        return false;
    }

    return dfs(s1, s2);
};
      

Problem Description

The Scramble String problem asks: given two strings s1 and s2 of the same length, determine if s2 is a scrambled version of s1.

A string is a scramble of another string if you can recursively partition it into two non-empty substrings, swap them (or not), and repeat the process on the substrings. At each step, you can choose to swap or not swap the two parts. The process continues recursively for each substring.

Constraints:

• Both s1 and s2 are of the same length.
• All characters are lowercase English letters.
• Every partition must be non-empty.
• You can swap or not swap at each partitioning step.

Thought Process

At first glance, the problem seems to ask for a check on whether the two strings can be transformed into each other by recursively swapping substrings. A brute-force approach would be to try all possible partitions and swaps, but this quickly becomes computationally expensive due to the exponential number of possibilities.

The challenge is to efficiently check all possible ways to partition and swap substrings, and to avoid redundant computation. We notice that many subproblems repeat themselves, so memoization (caching) can save us from recalculating the same scenario multiple times.

The key insight is that if two substrings are scrambled versions of each other, then their character counts must match. This allows us to prune impossible cases early, before recursing further.

Solution Approach

We solve the problem using recursion with memoization (top-down dynamic programming). Here are the steps:

1. Base Case: If the two substrings are identical, they are trivially scrambled versions of each other.
2. Pruning: If the sorted characters (or frequency counts) of the two substrings don't match, it's impossible for one to be a scramble of the other. We return false immediately.
3. Recursive Partitioning: For every possible split position, partition both strings into two non-empty parts. For each split, check:
   • Without swap: The first part of s1 matches the first part of s2 and the second part of s1 matches the second part of s2.
   • With swap: The first part of s1 matches the second part of s2 and vice versa.
   If either scenario is true, we return true.
4. Memoization: Store the result for each pair of substrings to avoid redundant work in future recursive calls.

This approach ensures that we only explore feasible paths and avoid repeated calculations, making the algorithm much more efficient.

Example Walkthrough

Let's consider s1 = "great" and s2 = "rgeat".

1. The strings are not identical, but their sorted characters match.
2. Try partitioning at position 1:
   • s1: "g" | "reat"
   • s2: "r" | "geat"
   • "g" ≠ "r", so try swapping: "g" vs "t" (last char of "geat") → not a match.
3. Try partitioning at position 2:
   • s1: "gr" | "eat"
   • s2: "rg" | "eat"
   • "gr" vs "rg" (same letters, possible scramble), "eat" vs "eat" (identical).
   • Recursively, "gr" and "rg" can be scrambled: split at 1 → "g" vs "r", "r" vs "g"; swapping gives a match.
   • So, overall, "great" and "rgeat" are scrambled versions.

The recursion explores all valid splits and swaps, but thanks to memoization and pruning, it avoids redundant or impossible paths.

Time and Space Complexity

Brute-force approach: Without memoization, the number of ways to partition and swap grows exponentially with the string length, leading to a time complexity of O(4^n) for strings of length n.

Optimized approach (with memoization): Each unique pair of substrings is computed at most once. There are O(n^4) possible pairs (since there are O(n^2) substrings for each string), and each computation involves O(n) work (for splitting and sorting/counting). Thus, the overall time complexity is O(n^4).

Space complexity: The memoization table stores results for O(n^4) substring pairs, so space complexity is also O(n^4).

In practice, pruning with character counts and memoization makes the solution efficient for reasonable string lengths.

Summary

The Scramble String problem is a classic example of recursive problem-solving with memoization. By breaking the problem into smaller subproblems, pruning impossible cases early, and caching results, we can efficiently determine whether two strings are scrambled versions of each other. The elegance of this solution lies in its combination of recursion, memoization, and early pruning, which together transform an exponential brute-force search into a tractable algorithm.