LeetCode 87: Scramble String

Top-down recursion with memoization & pruning を用いた分割統治アルゴリズム

1 アルゴリズム概要

Scramble String問題は、文字列がスクランブル変換によって別の文字列になり得るかを判定する問題です。 スクランブル変換では、文字列を任意の位置で分割し、左右の部分文字列を交換するかどうかを選択できます。

この問題の核心は分割統治です。文字列を全ての可能な位置で分割し、それぞれについて：

  1. 非交換パターン: s1[0:i] → s2[0:i], s1[i:] → s2[i:]
  2. 交換パターン: s1[0:i] → s2[len-i:], s1[i:] → s2[:len-i]

メモ化により重複計算を避け、文字頻度チェックによる枝刈りで効率化を図ります。

2 ステップバイステップ解説

実行ステップ

1

ベースケース判定

同じ文字列または長さ1の場合は即座にTrueを返す

2

文字頻度チェック

文字の出現頻度が異なる場合はスクランブル不可能

3

全分割点の試行

位置i（1からlen-1）で両方の文字列を分割

4

非交換パターン検査

s1[0:i]とs2[0:i]、s1[i:]とs2[i:]が一致するかチェック

5

交換パターン検査

s1[0:i]とs2[len-i:]、s1[i:]とs2[0:len-i]が一致するかチェック

6

メモ化と結果返却

結果をメモ辞書に保存し、最終答えを返す

ステップ解説図

ベースケース判定 if s1 == s2: return True 同じ文字列なら即座にTrue s1 = "ab" s2 = "ab" → True len(s) = 1 always True 文字頻度チェック（枝刈り） sorted(s1) == sorted(s2)? 頻度が異なる場合はスクランブル不可能 s1 = "great" s2 = "rgeat" 頻度一致 ✓ s1 = "abcd" s2 = "efgh" 頻度不一致 → False O(n log n) で効率的な枝刈り 全分割点の試行 i = 1 から len-1 まで分割位置を試す s1 = "great" g reat i=1: gr eat i=2: gre at i=3: grea t i=4: 各分割で2パターンをテスト 非交換パターン s1の左右 → s2の左右（順序保持） 例: i = 2 での分割 gr s1[0:2] eat s1[2:] vs rg s2[0:2] eat s2[2:] dfs("gr", "rg") AND dfs("eat", "eat") 両方ともTrueならこの分割でTrue 交換パターン s1の左右 → s2の右左（交換） 例: i = 2 での分割 gr s1[0:2] eat s1[2:] vs eat s2[3:] rg s2[0:3] dfs("gr", "rg") AND dfs("eat", "eat") クロスマッチング（交換後の一致） s2[len-i:] と s2[0:len-i] で分割 メモ化による最適化 memo[(s1, s2)] = result 重複計算を避けてO(n³)に最適化 メモリキャッシュ ("gr", "rg") → False ("eat", "eat") → True ("abc", "def") → False ("ab", "ba") → True 部分問題の結果を保存し、再利用 計算量改善 O(4^n) → O(n³) + O(n) stack

3 コード例

LeetCode形式のPython実装です。メモ化により重複計算を避け、文字頻度チェックによる枝刈りで効率化を図っています。 

class Solution:
    def isScramble(self, s1: str, s2: str) -> bool:
        memo = {}

        def dfs(s1, s2):
            # Base case: identical strings
            if s1 == s2:
                return True

            # Memoization check
            if (s1, s2) in memo:
                return memo[(s1, s2)]

            # Character frequency check (pruning)
            if sorted(s1) != sorted(s2):
                memo[(s1, s2)] = False
                return False

            # Try all possible split points
            for i in range(1, len(s1)):
                # No swap: s1[0:i] + s1[i:] vs s2[0:i] + s2[i:]
                if dfs(s1[:i], s2[:i]) and dfs(s1[i:], s2[i:]):
                    memo[(s1, s2)] = True
                    return True

                # Swap: s1[0:i] + s1[i:] vs s2[len-i:] + s2[:len-i]
                if dfs(s1[:i], s2[len(s1)-i:]) and dfs(s1[i:], s2[:len(s1)-i]):
                    memo[(s1, s2)] = True
                    return True

            memo[(s1, s2)] = False
            return False

        return dfs(s1, s2)

4 視覚的図解・フローチャート

アルゴリズムの全体的な流れを示すフローチャートです。分割統治の2つのパターン（非交換・交換）を明確に表現しています。

Start DFS dfs(s1, s2) s1 == s2? Return True In memo? Return memo[key] sorted(s1) == sorted(s2)? Return False Loop Split i = 1 to len-1 No-swap match? Swap match? Return True Return False Yes No Yes No No Yes Yes Yes All splits failed

5 計算量説明

時間計算量

O(4^n) → O(n³) with memoization

Without memoization: 各分割点で4つの再帰呼び出し（最悪）により指数時間
With memoization: 部分問題の数がO(n³)（異なる部分文字列の組み合わせ）

詳細分析:

  • 部分文字列のペア: O(n²)
  • 各ペアでの分割試行: O(n)
  • 頻度チェック（枝刈り）: O(n log n)

空間計算量

O(n³) for memoization + O(n) recursion stack

メモ化辞書が支配的。再帰の深さは最大O(n)なので、スタック使用量は比較的小さい

構成要素:

  • Memoization: O(n³) 個のキー
  • Recursion Stack: O(n) の深さ
  • String Slicing: O(n) の一時的な文字列

最適化のポイント

✅ 効果的な最適化
  • • メモ化: 重複計算の排除
  • • 頻度チェック: 不可能なケースの早期除外
  • • ベースケース: 同一文字列の即座判定
⚠️ 注意点
  • • 文字列スライシングのコスト
  • • メモリ使用量（長い文字列では問題になる可能性）
  • • sorted()による頻度チェックのコスト