LeetCode 2630 - Memoize II | ネストMap トライ構造

アルゴリズム概要

📋 問題の要件

任意の関数 fn を受け取り、 同じ引数列を2回渡した際に fn を再実行せずキャッシュから結果を返す ラッパー関数を生成します。

✓ 同一性判定は ===（参照同一性）
✓ 引数は任意の型・個数（0個も含む）
✓ fn が undefined を返すケースも正しくキャッシュ
✗ JSON.stringify キー化は不可（参照同一性が失われる）

🧠 解法の核心

MAP 引数を1つずつ Map のキー として辿るトライ木を構築

SYM Symbol キー で結果を格納。undefined 戻り値も has() で正確に判定

OBJ TrieNode オブジェクト不要。Map 自体がノード → オブジェクト生成コスト削減

// キャッシュ構造のイメージ

root → Map[arg0] → Map[arg1] → Map[RESULT] = value

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

TypeScript 実装

改善版：TrieNode オブジェクトを廃止し Map 自体をノードとして使用

type Fn = (...params: any) => any;

function memoize(fn: Fn): Fn {
    // Symbol をクロージャ内に閉じ込め、外部アクセスを防止
    // いかなる引数値とも衝突しないことをコンパイル時・実行時両方で保証
    const RESULT = Symbol('result');

    // ノード = Map 自体（TrieNodeオブジェクト不要）
    // 再帰型: 次の引数への経路 or 結果値を保持
    type CacheMap = Map<unknown, CacheMap | unknown>;

    const root: CacheMap = new Map();

    return function (...args: unknown[]): unknown {
        let node = root;

        // 各引数を順にトライを辿る
        // 経路がなければ新規 Map ノードを作成
        for (const arg of args) {
            if (!node.has(arg)) {
                node.set(arg, new Map() as CacheMap);
            }
            // 直前ブロックで set 済み → non-null assertion は安全
            node = node.get(arg) as CacheMap;
        }

        // 終端ノードにキャッシュがあればそれを返す
        // ※ has() で判定 → fn が undefined を返す場合も正確に動作
        if (node.has(RESULT)) {
            return node.get(RESULT); // キャッシュヒット: fn を呼ばない
        }

        // キャッシュミス: fn を実行して終端ノードに格納
        const result: unknown = fn(...args);
        node.set(RESULT, result);

        return result;
    };
}

フローチャート

フローの説明：
1. ラッパー関数が呼ばれると、root から引数を1つずつ Map でたどる
2. 経路上のノードが存在しなければ新規 Map を作成し、現在ノードを更新する（紫ループ）
3. 全引数を消費した終端ノードで has(RESULT) をチェック
4. キャッシュヒット（緑）なら即座に返す。キャッシュミス（赤）なら fn を実行して格納

計算量分析

時間計算量（1回の呼び出し）

O(k)

k = 引数の個数。各 Map 操作は O(1)

空間計算量（全体）

O(n·k)

n = ユニーク呼び出し数、k = 引数の個数

旧実装 vs 新実装（Map ノード化）の比較

比較項目	旧実装（TrieNode obj）	新実装（Map 直接）
ノード構造	{children:Map, hasResult, result}	Map のみ
オブジェクト生成	Object + Map（2重）	Map のみ
キャッシュ確認	node.hasResult（boolean）	map.has(RESULT)（Symbol）
undefined 戻り値	hasResult フラグが必要	has() で自然に対応
V8 JIT 親和性	Hidden Class 最適化が複雑	均一な Map 形状で最適化しやすい