Determine if s2 is a scrambled string of s1 (can split and swap subtrees recursively).
Input: s1="great", s2="rgeat" → Output: true
Input: s1="abcde", s2="caebd" → Output: false
Memoized recursion: for each split point, check both non-swap and swap cases.
- Base case: if s1==s2 return true; if sorted differs return false
- For each split length k (1 to n-1)
- Case 1 (no swap): isScramble(s1[0..k], s2[0..k]) AND isScramble(s1[k..], s2[k..])
- Case 2 (swap): isScramble(s1[0..k], s2[n-k..]) AND isScramble(s1[k..], s2[0..n-k])
- Memoize results
public boolean isScramble(String s1, String s2) {
if (s1.equals(s2)) return true;
Map<String, Boolean> memo = new HashMap<>();
return dfs(s1, s2, memo);
}
private boolean dfs(String s1, String s2, Map<String, Boolean> memo) {
String key = s1 + "#" + s2;
if (memo.containsKey(key)) return memo.get(key);
if (s1.equals(s2)) return true;
char[] a = s1.toCharArray(), 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 (dfs(s1.substring(0,k), s2.substring(0,k), memo) && dfs(s1.substring(k), s2.substring(k), memo) ||
dfs(s1.substring(0,k), s2.substring(n-k), memo) && dfs(s1.substring(k), s2.substring(0,n-k), memo)) {
memo.put(key, true); return true;
}
}
memo.put(key, false); return false;
}
- Time Complexity: O(n^4)
- Space Complexity: O(n^4)