Scrambled String Check
Problem
A string is scrambled like this: if it has one letter, stop; otherwise cut it at any point into two non-empty parts, optionally swap the two parts, and scramble each part the same way. Given two strings s1 and s2 of the same length, return whether s2 could come out of scrambling s1.
Examples
Input: s1 = "great", s2 = "rgeat"
Output: True
Why: cut into gr and eat, swap g and r inside gr, leave eat unchangedInput: s1 = "abcde", s2 = "caebd"
Output: FalseInput: s1 = "a", s2 = "a"
Output: True
Why: edge case, a single letter is its own only scrambleHints
0 / 3
Follow the definition. For s2 to be a scramble of s1, there must be a first cut position k and a choice of swapping or not, after which both halves are scrambles of each other.
Without swapping, s1's first k letters must match s2's first k letters. With swapping, s1's first k letters must match s2's last k letters. Each check is the same question on shorter strings.
Describe a subproblem by (start in s1, start in s2, length) and memoize it. Prune with a quick letter-count check: two pieces with different letters can never be scrambles of each other.
Solution
The definition is the recursion. For pieces of length n, try every cut k: either the first k letters of the s1 piece become the first k of the s2 piece and the rest become the rest, or the parts were swapped, and the first k letters of the s1 piece become the last k of the s2 piece. Plain recursion explodes because the same pair of pieces is asked about along many different paths, so the answer for each (start in s1, start in s2, length) triple is cached. The sorted-letters check cuts off most branches early, since a swap never changes which letters a piece contains. There are O(n³) subproblems and each tries O(n) cuts, so time is O(n⁴) in the worst case, and the cache takes O(n³) space.
from functools import lru_cache
def is_scramble(s1, s2):
if len(s1) != len(s2):
return False
@lru_cache(maxsize=None)
def same(i, j, n): # can s1[i:i+n] become s2[j:j+n]?
a, b = s1[i:i + n], s2[j:j + n]
if a == b:
return True
if sorted(a) != sorted(b): # different letters: no cut can fix that
return False
for k in range(1, n):
if same(i, j, k) and same(i + k, j + k, n - k): # parts kept in order
return True
if same(i, j + n - k, k) and same(i + k, j, n - k): # parts swapped
return True
return False
return same(0, 0, len(s1))
print(is_scramble("great", "rgeat")) # -> True
print(is_scramble("abcde", "caebd")) # -> False
print(is_scramble("a", "a")) # -> TrueStuck on the idea rather than the code? Memoization covers it.