Scramble string

String Dynamic Programming

44.0% acceptance

Jan 12, 2026

3615

1311

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. i.e., 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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;

impl Solution {
  pub fn is_scramble(s1: String, s2: String) -> bool {
    use std::collections::HashMap;
    let s1 = s1.as_bytes();
    let s2 = s2.as_bytes();
    let mut memo = HashMap::new();
    Self::helper_87(s1, s2, &mut memo)
  }
  
  fn helper_87(s1: &[u8], s2: &[u8], memo: &mut HashMap<(*const u8, *const u8, usize), bool>) -> bool {
    if s1 == s2 {
      return true;
    }
    let n = s1.len();
    if n != s2.len() || n == 0 {
      return false;
    }
    
    let key = (s1.as_ptr(), s2.as_ptr(), n);
    if let Some(&result) = memo.get(&key) {
      return result;
    }
    
    // Quick frequency check
    let mut freq = [0i8; 26];
    for i in 0..n {
      freq[(s1[i] - b'a') as usize] += 1;
      freq[(s2[i] - b'a') as usize] -= 1;
    }
    if freq.iter().any(|&f| f != 0) {
      memo.insert(key, false);
      return false;
    }
    
    for i in 1..n {
      // No swap
      if Self::helper_87(&s1[..i], &s2[..i], memo) && Self::helper_87(&s1[i..], &s2[i..], memo) {
        memo.insert(key, true);
        return true;
      }
      // Swap
      if Self::helper_87(&s1[..i], &s2[n-i..], memo) && Self::helper_87(&s1[i..], &s2[..n-i], memo) {
        memo.insert(key, true);
        return true;
      }
    }
    
    memo.insert(key, false);
    false
  }
}