アルゴリズム概要
-
二分割＋スワップの再帰で生成できる文字列集合に
s2が含まれるか判定。 -
再帰 + メモ化：部分問題
(i1, i2, len)をキャッシュし重複計算を回避。 - 頻度枝刈り：区間の 26-bin 文字頻度差が非ゼロなら即不一致。
- 完全一致の早期終了：区間が等しければ分割不要で True。
ステップバイステップ
図解
ステップ1: 入力長の確認
len(s1) と len(s2) の長さを比較
一致していればスクランブル判定を継続。 入力サイズが揃っていることをまず確認します。
長さが異なる → False を返す
長さが違う文字列からスクランブル生成は不可能。 その場で探索を終了します。
コード例（Python / LeetCode形式）
from __future__ import annotations
from functools import lru_cache
from typing import Final
class Solution:
"""
87. Scramble String
トップダウン再帰 + メモ化 + 頻度枝刈り + 完全一致早期判定
- Pure: 外部状態なし
- 型注釈: pylance対応
"""
def isScramble(self, s1: str, s2: str) -> bool:
"""
判定関数（LeetCode規定シグネチャ）
Args:
s1: 元文字列（a-z, 1..30）
s2: 判定対象（a-z, 1..30, len(s1) == len(s2)）
Returns:
bool: s2 が s1 のスクランブルで生成可能なら True
Complexity:
Time: O(n^4) worst, Space: O(n^3) (n = len(s1))
"""
n: int = len(s1)
if n != len(s2):
return False
if s1 == s2:
return True
OA: Final[int] = ord("a")
def same_multiset(i1: int, i2: int, length: int) -> bool:
cnt = [0] * 26
for k in range(length):
cnt[ord(s1[i1 + k]) - OA] += 1
cnt[ord(s2[i2 + k]) - OA] -= 1
for v in cnt:
if v != 0:
return False
return True
def equal(i1: int, i2: int, length: int) -> bool:
for k in range(length):
if s1[i1 + k] != s2[i2 + k]:
return False
return True
if not same_multiset(0, 0, n):
return False
@lru_cache(maxsize=いいえne)
def dfs(i1: int, i2: int, length: int) -> bool:
if equal(i1, i2, length):
return True
if not same_multiset(i1, i2, length):
return False
for cut in range(1, length):
if dfs(i1, i2, cut) and dfs(i1 + cut, i2 + cut, length - cut):
return True
if dfs(i1, i2 + (length - cut), cut) and dfs(i1 + cut, i2, length - cut):
return True
return False
return dfs(0, 0, n)視覚的図解・フローチャート（概要）
開始 → 完全一致 → 頻度チェック → cut ループ → 非スワップ／スワップの 成否 → cut++ / 全滅で False という Mermaid 図と同じ流れを見やすく配置し ています。
計算量
- Time: O(n4)（cut × 2 分岐 × 区間組の組み合わせ。メモ化 & 枝刈りで実用的）
- Space: O(n3)（メモ化テーブル＋再帰スタック）