We define a scramble process on a string recursively: split it at some point and optionally swap the two halves, then recursively scramble each part. Given s1 and s2, return true if s2 is a scramble of s1.
Input: s1="great", s2="rgeat" → Output: trueInput: s1="abcde", s2="caebd" → Output: false
Use memoization: isScramble(s1,s2) tries all split points. For each split at k: either (no swap) first k of s1 matches first k of s2 AND rest matches; or (swap) first k of s1 matches last k of s2 AND rest matches.
- Base: if s1==s2 return true. If sorted chars differ return false.
- For each split length k from 1 to n-1:
- No swap: isScramble(s1[0..k], s2[0..k]) && isScramble(s1[k..], s2[k..]).
- Swap: isScramble(s1[0..k], s2[n-k..]) && isScramble(s1[k..], s2[0..n-k]).
import java.util.*;
class Solution {
Map<String,Boolean> memo = new HashMap<>();
public boolean isScramble(String s1, String s2) {
if (s1.equals(s2)) return true;
String key = s1 + "#" + s2;
if (memo.containsKey(key)) return memo.get(key);
char[] c1 = s1.toCharArray(), c2 = s2.toCharArray();
Arrays.sort(c1); Arrays.sort(c2);
if (!new String(c1).equals(new String(c2))) { 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))) ||
(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;
}
}
- Time Complexity: O(N^4) with memoization
- Space Complexity: O(N^3) memo states