LeetCode 87: Scramble String (Interval DP / Memoized Split Recursion)
LeetCode 87StringDPMemoizationToday we solve LeetCode 87 - Scramble String.
Source: https://leetcode.com/problems/scramble-string/
English
Problem Summary
Given two strings s1 and s2 of equal length, determine whether s2 can be formed by recursively splitting s1 into two non-empty parts and optionally swapping the two children at any internal split.
Key Insight
For interval s1[i:i+len) and s2[j:j+len), try every split k. Two valid transitions exist: no-swap and swap. Use memoization on state (i, j, len) to avoid exponential recomputation, and do a quick character-frequency pruning before split loops.
Brute Force and Limitations
Pure recursion explores all binary split trees and both swap/non-swap branches at every node, which explodes combinatorially. Without memoization and pruning, it times out quickly.
Optimal Algorithm Steps
1) If substrings are exactly equal, return true.
2) If character multiset differs, return false immediately.
3) For each split k = 1..len-1, check:
- No swap: dfs(i, j, k) && dfs(i+k, j+k, len-k)
- Swap: dfs(i, j+len-k, k) && dfs(i+k, j, len-k)
4) Cache and return result for (i,j,len).
Complexity Analysis
Let n be string length.
States: O(n^3) for (i,j,len).
Transition per state: up to O(n) splits, with frequency check O(26).
Total: O(n^4) time, O(n^3) space.
Common Pitfalls
- Missing frequency pruning, causing huge branch expansion.
- Forgetting swapped case and only testing aligned splits.
- Wrong memo key (must include both starts and length).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
private String s1, s2;
private byte[][][] memo; // 0 unknown, 1 true, -1 false
public boolean isScramble(String s1, String s2) {
if (s1.length() != s2.length()) return false;
this.s1 = s1;
this.s2 = s2;
int n = s1.length();
memo = new byte[n][n][n + 1];
return dfs(0, 0, n);
}
private boolean dfs(int i, int j, int len) {
if (memo[i][j][len] != 0) return memo[i][j][len] == 1;
if (s1.regionMatches(i, s2, j, len)) {
memo[i][j][len] = 1;
return true;
}
int[] cnt = new int[26];
for (int p = 0; p < len; p++) {
cnt[s1.charAt(i + p) - 'a']++;
cnt[s2.charAt(j + p) - 'a']--;
}
for (int c : cnt) {
if (c != 0) {
memo[i][j][len] = -1;
return false;
}
}
for (int k = 1; k < len; k++) {
if (dfs(i, j, k) && dfs(i + k, j + k, len - k) ||
dfs(i, j + len - k, k) && dfs(i + k, j, len - k)) {
memo[i][j][len] = 1;
return true;
}
}
memo[i][j][len] = -1;
return false;
}
}func isScramble(s1 string, s2 string) bool {
n := len(s1)
if n != len(s2) {
return false
}
memo := make([][][]int8, n)
for i := 0; i < n; i++ {
memo[i] = make([][]int8, n)
for j := 0; j < n; j++ {
memo[i][j] = make([]int8, n+1)
}
}
var dfs func(i, j, l int) bool
dfs = func(i, j, l int) bool {
if memo[i][j][l] != 0 {
return memo[i][j][l] == 1
}
if s1[i:i+l] == s2[j:j+l] {
memo[i][j][l] = 1
return true
}
var cnt [26]int
for p := 0; p < l; p++ {
cnt[s1[i+p]-'a']++
cnt[s2[j+p]-'a']--
}
for _, v := range cnt {
if v != 0 {
memo[i][j][l] = -1
return false
}
}
for k := 1; k < l; k++ {
if (dfs(i, j, k) && dfs(i+k, j+k, l-k)) ||
(dfs(i, j+l-k, k) && dfs(i+k, j, l-k)) {
memo[i][j][l] = 1
return true
}
}
memo[i][j][l] = -1
return false
}
return dfs(0, 0, n)
}class Solution {
public:
string a, b;
vector>> memo;
bool isScramble(string s1, string s2) {
if (s1.size() != s2.size()) return false;
a = s1; b = s2;
int n = a.size();
memo.assign(n, vector>(n, vector(n + 1, 0)));
return dfs(0, 0, n);
}
bool dfs(int i, int j, int len) {
if (memo[i][j][len] != 0) return memo[i][j][len] == 1;
if (a.compare(i, len, b, j, len) == 0) {
memo[i][j][len] = 1;
return true;
}
int cnt[26] = {0};
for (int p = 0; p < len; ++p) {
cnt[a[i + p] - 'a']++;
cnt[b[j + p] - 'a']--;
}
for (int c : cnt) {
if (c != 0) {
memo[i][j][len] = -1;
return false;
}
}
for (int k = 1; k < len; ++k) {
if ((dfs(i, j, k) && dfs(i + k, j + k, len - k)) ||
(dfs(i, j + len - k, k) && dfs(i + k, j, len - k))) {
memo[i][j][len] = 1;
return true;
}
}
memo[i][j][len] = -1;
return false;
}
}; from functools import lru_cache
class Solution:
def isScramble(self, s1: str, s2: str) -> bool:
if len(s1) != len(s2):
return False
@lru_cache(None)
def dfs(i: int, j: int, l: int) -> bool:
if s1[i:i + l] == s2[j:j + l]:
return True
cnt = [0] * 26
for p in range(l):
cnt[ord(s1[i + p]) - 97] += 1
cnt[ord(s2[j + p]) - 97] -= 1
if any(cnt):
return False
for k in range(1, l):
if dfs(i, j, k) and dfs(i + k, j + k, l - k):
return True
if dfs(i, j + l - k, k) and dfs(i + k, j, l - k):
return True
return False
return dfs(0, 0, len(s1))var isScramble = function(s1, s2) {
const n = s1.length;
if (n !== s2.length) return false;
const memo = new Map();
function dfs(i, j, len) {
const key = `${i}#${j}#${len}`;
if (memo.has(key)) return memo.get(key);
if (s1.slice(i, i + len) === s2.slice(j, j + len)) {
memo.set(key, true);
return true;
}
const cnt = new Array(26).fill(0);
for (let p = 0; p < len; p++) {
cnt[s1.charCodeAt(i + p) - 97]++;
cnt[s2.charCodeAt(j + p) - 97]--;
}
if (cnt.some(v => v !== 0)) {
memo.set(key, false);
return false;
}
for (let k = 1; k < len; k++) {
if ((dfs(i, j, k) && dfs(i + k, j + k, len - k)) ||
(dfs(i, j + len - k, k) && dfs(i + k, j, len - k))) {
memo.set(key, true);
return true;
}
}
memo.set(key, false);
return false;
}
return dfs(0, 0, n);
};中文
题目概述
给定两个等长字符串 s1 和 s2，判断 s2 是否可以由 s1 递归切分并在任意内部节点进行左右子串交换后得到。
核心思路
定义状态 dfs(i, j, len)：判断 s1[i:i+len) 与 s2[j:j+len) 是否互为 scramble。每个切分点 k 有两种转移：不交换、交换。用记忆化缓存状态，外加字符频次剪枝，显著减少搜索空间。
暴力解法与不足
纯递归会尝试所有切分树与交换组合，分支数量爆炸；没有缓存和剪枝基本会超时。
最优算法步骤
1）若两段子串完全相同，直接返回 true。
2）先做 26 字母频次对比，不同则直接 false。
3）枚举切分点 k：
- 不交换：dfs(i, j, k) && dfs(i+k, j+k, len-k)
- 交换：dfs(i, j+len-k, k) && dfs(i+k, j, len-k)
4）把结果写入缓存并返回。
复杂度分析
设字符串长度为 n。状态数 O(n^3)，每个状态枚举切分点 O(n)，总体时间 O(n^4)，空间 O(n^3)。
常见陷阱
- 忘记频次剪枝，导致大量无效递归。
- 只写了“不交换”分支，漏掉“交换”分支。
- 缓存键不完整（必须包含 i、j、len）。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
private String s1, s2;
private byte[][][] memo; // 0 unknown, 1 true, -1 false
public boolean isScramble(String s1, String s2) {
if (s1.length() != s2.length()) return false;
this.s1 = s1;
this.s2 = s2;
int n = s1.length();
memo = new byte[n][n][n + 1];
return dfs(0, 0, n);
}
private boolean dfs(int i, int j, int len) {
if (memo[i][j][len] != 0) return memo[i][j][len] == 1;
if (s1.regionMatches(i, s2, j, len)) {
memo[i][j][len] = 1;
return true;
}
int[] cnt = new int[26];
for (int p = 0; p < len; p++) {
cnt[s1.charAt(i + p) - 'a']++;
cnt[s2.charAt(j + p) - 'a']--;
}
for (int c : cnt) {
if (c != 0) {
memo[i][j][len] = -1;
return false;
}
}
for (int k = 1; k < len; k++) {
if (dfs(i, j, k) && dfs(i + k, j + k, len - k) ||
dfs(i, j + len - k, k) && dfs(i + k, j, len - k)) {
memo[i][j][len] = 1;
return true;
}
}
memo[i][j][len] = -1;
return false;
}
}func isScramble(s1 string, s2 string) bool {
n := len(s1)
if n != len(s2) {
return false
}
memo := make([][][]int8, n)
for i := 0; i < n; i++ {
memo[i] = make([][]int8, n)
for j := 0; j < n; j++ {
memo[i][j] = make([]int8, n+1)
}
}
var dfs func(i, j, l int) bool
dfs = func(i, j, l int) bool {
if memo[i][j][l] != 0 {
return memo[i][j][l] == 1
}
if s1[i:i+l] == s2[j:j+l] {
memo[i][j][l] = 1
return true
}
var cnt [26]int
for p := 0; p < l; p++ {
cnt[s1[i+p]-'a']++
cnt[s2[j+p]-'a']--
}
for _, v := range cnt {
if v != 0 {
memo[i][j][l] = -1
return false
}
}
for k := 1; k < l; k++ {
if (dfs(i, j, k) && dfs(i+k, j+k, l-k)) ||
(dfs(i, j+l-k, k) && dfs(i+k, j, l-k)) {
memo[i][j][l] = 1
return true
}
}
memo[i][j][l] = -1
return false
}
return dfs(0, 0, n)
}class Solution {
public:
string a, b;
vector>> memo;
bool isScramble(string s1, string s2) {
if (s1.size() != s2.size()) return false;
a = s1; b = s2;
int n = a.size();
memo.assign(n, vector>(n, vector(n + 1, 0)));
return dfs(0, 0, n);
}
bool dfs(int i, int j, int len) {
if (memo[i][j][len] != 0) return memo[i][j][len] == 1;
if (a.compare(i, len, b, j, len) == 0) {
memo[i][j][len] = 1;
return true;
}
int cnt[26] = {0};
for (int p = 0; p < len; ++p) {
cnt[a[i + p] - 'a']++;
cnt[b[j + p] - 'a']--;
}
for (int c : cnt) {
if (c != 0) {
memo[i][j][len] = -1;
return false;
}
}
for (int k = 1; k < len; ++k) {
if ((dfs(i, j, k) && dfs(i + k, j + k, len - k)) ||
(dfs(i, j + len - k, k) && dfs(i + k, j, len - k))) {
memo[i][j][len] = 1;
return true;
}
}
memo[i][j][len] = -1;
return false;
}
}; from functools import lru_cache
class Solution:
def isScramble(self, s1: str, s2: str) -> bool:
if len(s1) != len(s2):
return False
@lru_cache(None)
def dfs(i: int, j: int, l: int) -> bool:
if s1[i:i + l] == s2[j:j + l]:
return True
cnt = [0] * 26
for p in range(l):
cnt[ord(s1[i + p]) - 97] += 1
cnt[ord(s2[j + p]) - 97] -= 1
if any(cnt):
return False
for k in range(1, l):
if dfs(i, j, k) and dfs(i + k, j + k, l - k):
return True
if dfs(i, j + l - k, k) and dfs(i + k, j, l - k):
return True
return False
return dfs(0, 0, len(s1))var isScramble = function(s1, s2) {
const n = s1.length;
if (n !== s2.length) return false;
const memo = new Map();
function dfs(i, j, len) {
const key = `${i}#${j}#${len}`;
if (memo.has(key)) return memo.get(key);
if (s1.slice(i, i + len) === s2.slice(j, j + len)) {
memo.set(key, true);
return true;
}
const cnt = new Array(26).fill(0);
for (let p = 0; p < len; p++) {
cnt[s1.charCodeAt(i + p) - 97]++;
cnt[s2.charCodeAt(j + p) - 97]--;
}
if (cnt.some(v => v !== 0)) {
memo.set(key, false);
return false;
}
for (let k = 1; k < len; k++) {
if ((dfs(i, j, k) && dfs(i + k, j + k, len - k)) ||
(dfs(i, j + len - k, k) && dfs(i + k, j, len - k))) {
memo.set(key, true);
return true;
}
}
memo.set(key, false);
return false;
}
return dfs(0, 0, n);
};
Comments