Scramble String
Problem
String s2 is a scramble of s1 if for some split k, either (left1 scrambles left2 AND right1 scrambles right2), or (left1 scrambles right2 AND right1 scrambles left2). Return whether s2 is a scramble of s1.
s1 = "great", s2 = "rgeat"truefrom functools import lru_cache
def is_scramble(s1, s2):
@lru_cache(maxsize=None)
def go(a, b):
if a == b:
return True
if sorted(a) != sorted(b):
return False
n = len(a)
for k in range(1, n):
if go(a[:k], b[:k]) and go(a[k:], b[k:]):
return True
if go(a[:k], b[n - k:]) and go(a[k:], b[:n - k]):
return True
return False
return go(s1, s2)function isScramble(s1, s2) {
const memo = new Map();
function go(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 k = 1; k < n; k++) {
if (go(a.slice(0, k), b.slice(0, k)) && go(a.slice(k), b.slice(k))) { memo.set(key, true); return true; }
if (go(a.slice(0, k), b.slice(n - k)) && go(a.slice(k), b.slice(0, n - k))) { memo.set(key, true); return true; }
}
memo.set(key, false);
return false;
}
return go(s1, s2);
}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[] a = s1.toCharArray();
char[] b = s2.toCharArray();
Arrays.sort(a); Arrays.sort(b);
if (!Arrays.equals(a, b)) { memo.put(key, false); return false; }
int n = s1.length();
for (int k = 1; k < n; k++) {
if (isScramble(s1.substring(0, k), s2.substring(0, k))
&& isScramble(s1.substring(k), s2.substring(k))) { memo.put(key, true); return true; }
if (isScramble(s1.substring(0, k), s2.substring(n - k))
&& isScramble(s1.substring(k), s2.substring(0, n - k))) { memo.put(key, true); return true; }
}
memo.put(key, false);
return false;
}
}unordered_map<string, bool> memo;
bool isScramble(string s1, string s2) {
string key = s1 + "|" + s2;
auto it = memo.find(key);
if (it != memo.end()) return it->second;
if (s1 == s2) return memo[key] = true;
string a = s1, b = s2;
sort(a.begin(), a.end()); sort(b.begin(), b.end());
if (a != b) return memo[key] = false;
int n = s1.size();
for (int k = 1; k < n; k++) {
if (isScramble(s1.substr(0, k), s2.substr(0, k))
&& isScramble(s1.substr(k), s2.substr(k))) return memo[key] = true;
if (isScramble(s1.substr(0, k), s2.substr(n - k))
&& isScramble(s1.substr(k), s2.substr(0, n - k))) return memo[key] = true;
}
return memo[key] = false;
}Explanation
A scramble is built by recursively splitting a string into two parts and optionally swapping the two halves. So to test if s2 is a scramble of s1, we try every split point and recurse on the pieces.
Two quick checks prune most work. If the two strings are already equal, return true. If their letters sorted differently, they can never be scrambles, so return false — this kills hopeless branches early.
For each split position k, there are two layouts. No swap: the left k of s1 must scramble the left k of s2, and the right parts must match too. Swap: the left of s1 must scramble the last k characters of s2, and the right of s1 the first part. If any split works either way, the answer is true.
Because the same substring pairs come up again and again, we memoize results keyed by the two pieces, turning exponential recursion into something manageable.
Example: s1 = "great", s2 = "rgeat". Split "great" into "g" + "reat"; "reat" scrambles to itself and then the two halves swap to produce "rgeat", so the result is true.