87. Scramble String
Call a string t a scramble of a string s when t can be produced by this recursive shuffle: if s is a single character, t must be that same character. Otherwise, cut s at any position into two non-empty pieces s = left + right, choose (independently at every level of the recursion) whether to swap the two pieces, and recursively scramble each piece.
You receive two lowercase strings s1 and s2 of equal length. Return true if s2 is a scramble of s1, and false otherwise.
Example 1:
Input: s1 = "great", s2 = "rgeat"
Output: true
Explanation: Cut "great" into "gr" + "eat" and keep the pieces in place. Inside the first piece, cut "gr" into "g" + "r" and swap them to get "rg". Leave "eat" alone. The result is "rg" + "eat" = "rgeat".
Example 2:
Input: s1 = "abcde", s2 = "caebd"
Output: false
Explanation: No sequence of cuts and swaps turns "abcde" into "caebd" — every split point fails both the no-swap and the swap pairing.
Constraints:
- 1 ≤ s1.length ≤ 30
- s2.length == s1.length
- s1 and s2 consist of lowercase English letters
Hints:
Think recursively, exactly like the definition. For a window of length `len`, some cut `k` (1 <= k < len) must work in one of two ways: the first `k` characters of the s1-window match up with the **first** `k` of the s2-window (no swap), or with the **last** `k` of the s2-window (swap). Each option splits the problem into two smaller ones.
A subproblem is fully described by three numbers — start in s1, start in s2, window length — so the same triple recurs constantly. Memoize it, and prune aggressively: if the two windows do not contain the same multiset of letters, no scramble can ever succeed.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s1 = "great", s2 = "rgeat"
Expected output: true