Scramble String
Solve this Problems1 and s2, determine whether s2 can be produced from s1 by repeatedly picking any remaining piece, splitting it into two non-empty halves, and optionally swapping those halves — applied recursively, as many times as needed.
Two strings are scrambles of each other exactly when they're already identical, or when some split of both at the same position lines up either straight (first-with-first, second-with-second) or swapped (first-with-second, second-with-first) — each side itself checked recursively by the same rule. That recursion is correct on its own, but it keeps re-solving the same pair of substrings from scratch every time it's reached through a different sequence of splits. Caching the answer for every (substring of s1, substring of s2) pair the first time it's computed turns that repeated work into a one-time cost per pair — and there are only a polynomial number of such pairs, since a substring is fully described by just a start position and a length.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ s1.length ≤ 20 - ◆
s2.length == s1.length - ◆
s1 and s2 consist of lowercase English letters
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Recursion Without Memoization
BruteTwo equal-length strings are scrambles of each other exactly when they're identical outright, or when there's some way to split both at the same position into a first half and second half such that either (first half of s1 scrambles into first half of s2, and second into second) or (first half of s1 scrambles into the *second* half of s2, and second into the *first*) — that second case is what a swap at this split looks like. Trying every split position and recursing both ways is correct, but it re-derives the same substring pair's answer over and over across different recursive paths, so the cost roughly doubles with every added character.
O(2ⁿ)O(n)1class Solution {
2 public boolean isScramble(String s1, String s2) {
3 if (s1.length() != s2.length()) return false;
4 if (s1.equals(s2)) return true;
5
6 int n = s1.length();
7 int[] count = new int[26];
8 for (int i = 0; i < n; i++) {
9 count[s1.charAt(i) - 'a']++;
10 count[s2.charAt(i) - 'a']--;
11 }
12 for (int c : count) {
13 if (c != 0) return false;
14 }
15
16 for (int i = 1; i < n; i++) {
17 if (isScramble(s1.substring(0, i), s2.substring(0, i)) && isScramble(s1.substring(i), s2.substring(i))) {
18 return true;
19 }
20 if (isScramble(s1.substring(0, i), s2.substring(n - i)) && isScramble(s1.substring(i), s2.substring(0, n - i))) {
21 return true;
22 }
23 }
24 return false;
25 }
26}Optimal — Top-Down Memoization
OptimalThe recursion itself doesn't change at all — it's the exact same "try every split, check the swapped and non-swapped arrangement" logic. What changes is remembering the answer for every (substring of s1, substring of s2) pair the first time it's worked out, keyed by the two substrings themselves, so any later call asking the exact same question gets the cached answer instead of re-deriving it. There are only O(n³) distinct substring-pair combinations possible (a start and length for each string, constrained to equal lengths), so the total work collapses from exponential to polynomial.
O(n⁴)O(n³)1class Solution {
2 private Map<String, Boolean> memo = new HashMap<>();
3
4 public boolean isScramble(String s1, String s2) {
5 memo = new HashMap<>();
6 return solve(s1, s2);
7 }
8
9 private boolean solve(String s1, String s2) {
10 if (s1.equals(s2)) return true;
11 String key = s1 + "#" + s2;
12 if (memo.containsKey(key)) return memo.get(key);
13
14 int n = s1.length();
15 int[] count = new int[26];
16 for (int i = 0; i < n; i++) {
17 count[s1.charAt(i) - 'a']++;
18 count[s2.charAt(i) - 'a']--;
19 }
20 for (int c : count) {
21 if (c != 0) {
22 memo.put(key, false);
23 return false;
24 }
25 }
26
27 for (int i = 1; i < n; i++) {
28 if (solve(s1.substring(0, i), s2.substring(0, i)) && solve(s1.substring(i), s2.substring(i))) {
29 memo.put(key, true);
30 return true;
31 }
32 if (solve(s1.substring(0, i), s2.substring(n - i)) && solve(s1.substring(i), s2.substring(0, n - i))) {
33 memo.put(key, true);
34 return true;
35 }
36 }
37 memo.put(key, false);
38 return false;
39 }
40}