87. Scramble String

Time: O(n^4)

Space: O(n^3)

Intuition

A string t is a scramble of s if there exists a split point k such that either: (s[0..k] scrambles to t[0..k] AND s[k+1..] scrambles to t[k+1..]), or (s[0..k] scrambles to t[n-k..] AND s[k+1..] scrambles to t[0..n-k-1]). Memoize on (s, t) pairs.

Algorithm

1If s == t, return true. If sorted(s) != sorted(t), return false (fast prune).
2Check memo map for (s, t).
3For k from 1 to n-1: try both the non-swapped split and the swapped split.
4If any k satisfies either condition, store true in memo and return true.
5Store false and return false.

Example Walkthrough

Input: s = "great", t = "rgeat"

1.Try k=1: s[0..0]="g", t[0..0]="r" not scramble. s[0..0]="g" vs t[4..4]="t" - no.
2.Try k=2: s[0..1]="gr" vs t[0..1]="rg" - yes (swapped). s[2..4]="eat" vs t[2..4]="eat" - yes.
3.Return true.

Output: true

Common Pitfalls

•The anagram check (sorted chars equal) prunes many impossible branches quickly.
•Use a Dictionary<(string,string), bool> for memoization.

87.cs

// Approach: Memoized recursion splitting the string at every index.
// Prune early by checking that both halves have matching character frequencies.
// Time: O(n^4) Space: O(n^3)

public class Solution
{
    private Dictionary<string, bool> mem = new Dictionary<string, bool>();

    public bool IsScramble(string s1, string s2)
    {
        if (s1.Equals(s2))
            return true;
        string hashKey = s1 + "+" + s2;
        if (mem.ContainsKey(hashKey))
            return mem[hashKey];

        int[] count = new int[128];

        for (int i = 0; i < s1.Length; ++i)
        {
            ++count[s1[i]];
            --count[s2[i]];
        }

        foreach (int freq in count)
        {
            if (freq != 0)
            {
                mem[hashKey] = false;
                return false;
            }
        }

        for (int i = 1; i < s1.Length; ++i)
        {
            if (IsScramble(s1.Substring(0, i), s2.Substring(0, i)) &&
                IsScramble(s1.Substring(i), s2.Substring(i)))
            {
                mem[hashKey] = true;
                return true;
            }
            if (IsScramble(s1.Substring(0, i), s2.Substring(s2.Length - i)) &&
                IsScramble(s1.Substring(i), s2.Substring(0, s2.Length - i)))
            {
                mem[hashKey] = true;
                return true;
            }
        }

        mem[hashKey] = false;
        return false;
    }
}

Was this solution helpful?