Skip to main content

87. Scramble String

hard

Determine whether s2 is a scramble of s1, where scrambling means recursively splitting and optionally swapping halves. A purely structural recursion problem — split, branch, memoize.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

We can scramble a string s to get a string t using the following algorithm: If the length of the string is 1, stop. If the length of the string is > 1, do the following: Split the string into two non-empty substrings at a random index, i.e., if the string is s, divide it to x and y where s = x + y. Randomly decide to swap the two substrings or to keep them in the same order. So, after this step, s may become s = x + y or s = y + x. Apply step 1 recursively on each of the two substrings x and y. Given two strings s1 and s2 of the same length, return true if s2 is a scrambled string of s1, otherwise, return false.

Constraints

  • s1.length == s2.length
  • 1 <= s1.length <= 30
  • s1 and s2 consist of lowercase English letters.

Examples

Example 1

Input
s1 = "great", s2 = "rgeat"
Output
true

Example 2

Input
s1 = "abcde", s2 = "caebd"
Output
false

Example 3

Input
s1 = "a", s2 = "a"
Output
true

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

If s1 == s2 -> true. If sorted(s1) != sorted(s2) -> false (cheap reject — characters must match).

Hint 2

Try every split point i from 1 to length - 1.

Hint 3

Case 1 (no swap): s1[..i] scrambles to s2[..i] AND s1[i..] scrambles to s2[i..].

Hint 4

Case 2 (swap): s1[..i] scrambles to s2[len-i..] AND s1[i..] scrambles to s2[..len-i]. Memoize on (s1, s2).

Solution approach

Reveal approach

Recursive isScramble(s1, s2): if s1 == s2 return true; if char counts differ, return false (pre-check rejects clearly impossible cases). For each split point i from 1 to length - 1: case 1 (no swap) — recurse on (s1[..i], s2[..i]) and (s1[i..], s2[i..]); case 2 (swap) — recurse on (s1[..i], s2[len-i..]) and (s1[i..], s2[..len-i]). If any combination succeeds, return true. Memoize on (s1, s2) string pair — same input always gives the same answer. Time is O(n^4) memoized (n^2 substring pairs times O(n) split points times O(n) recursion); space O(n^3) for the memo.

Complexity

Time
O(n^4)
Space
O(n^3)

Related patterns

  • recursion
  • memoization
  • string-partition

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google
  • Amazon

More Recursion practice problems

See all Recursion problems →