問題 208：Trie（接頭辞木）の実装

Trie（トライ、発音は「トライ」に近い）または接頭辞木は、文字列のデータセットを効率的に保存および検索するための木構造データ構造です。このデータ構造は、オートコンプリートやスペルチェックなど、多くの応用シーンで使用されます。

以下の操作をサポートする Trie クラスを実装してください。

• Trie() - 接頭辞木オブジェクトを初期化します。
• void insert(String word) - 文字列 word を接頭辞木に挿入します。
• boolean search(String word) - 文字列 word が接頭辞木に存在する場合、true を返します（挿入済みであることを意味します）。それ以外の場合は false を返します。
• boolean startsWith(String prefix) - 以前に挿入された文字列 word のいずれかの接頭辞が prefix である場合、true を返します。それ以外の場合は false を返します。

例：

入力
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]

出力
[null, null, true, false, true, null, true]

説明
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // true を返す
trie.search("app");     // false を返す
trie.startsWith("app"); // true を返す
trie.insert("app");
trie.search("app");     // true を返す

制約：

• 1 <= word.length, prefix.length <= 2000
• word と prefix は小文字の英字のみで構成されます。
• insert、search、および startsWith の呼び出し総数は 3 * 10^4 を超えません。

問題の分析

問題の分解

1. この問題は、オートコンプリートやスペルチェックなどの機能を実現するための、高性能な検索システムを作成することを目的としています。 2. 基本的な設計方針は、単語を反復処理し、各レベルで辞書（マップ）を使用して保存することです。同時に、単語の終わりを示す情報も保存する必要があります（search は終わりを検出し、startsWith は検出しません）。

最適化のアイデア

1. データ構造の選択：単語の各文字をキーとして、次のノードへの参照を値として保存する辞書（または配列）が適しています。 2. 文字セットの特性：問題文では小文字の英字のみが使用されるため、26文字分の配列や辞書で各レベルを表現できます。ASCII文字セット全体をサポートする場合は、128要素の配列も有効です。 3. 単語の終わりのマーカー：単語の終わりを示すために、辞書内に特別なキー（例: '_end_'）を追加する方法がシンプルで効率的です。

コード実装

ここでは、3つの異なる実装アプローチを紹介します。それぞれのパフォーマンスとメモリ使用量は異なります。

1. 標準的な実装（ノードクラス + 辞書）

各ノードを表すクラスを作成し、子ノードを辞書で管理します。単語の終わりを示すフラグもノードに持たせます。

class TrieNode:
    def __init__(self):
        self.children = {}  # 子ノードを辞書で管理
        self.is_end_of_word = False  # 単語の終わりを示すフラグ

class TrieV1:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        current_node = self.root
        for char in word:
            # 文字が存在しない場合は新しいノードを作成
            if char not in current_node.children:
                current_node.children[char] = TrieNode()
            current_node = current_node.children[char]
        current_node.is_end_of_word = True

    def search(self, word: str) -> bool:
        current_node = self.root
        for char in word:
            if char not in current_node.children:
                return False
            current_node = current_node.children[char]
        return current_node.is_end_of_word

    def startsWith(self, prefix: str) -> bool:
        current_node = self.root
        for char in prefix:
            if char not in current_node.children:
                return False
            current_node = current_node.children[char]
        return True

2. 改良版（固定サイズ配列 + ノードクラス）

文字セットがASCIIに限定されていることを利用し、子ノードを固定サイズのリストで管理します。これにより、辞書のハッシュ計算オーバーヘッドを削減できます。

class TrieV2:
    def __init__(self):
        self.root = [None] * 128  # ASCII文字セット（0-127）用の配列

    def insert(self, word: str) -> None:
        current = self.root
        for char in word:
            char_code = ord(char)
            if current[char_code] is None:
                current[char_code] = [None] * 128  # 新しいレベルの配列を作成
            current = current[char_code]
        # 単語の終わりを示すために特別な値を設定
        current[ord('_')] = True

    def search(self, word: str) -> bool:
        current = self.root
        for char in word:
            char_code = ord(char)
            if current[char_code] is None:
                return False
            current = current[char_code]
        # 単語の終わりマーカーが存在するか確認
        return current[ord('_')] is True

    def startsWith(self, prefix: str) -> bool:
        current = self.root
        for char in prefix:
            char_code = ord(char)
            if current[char_code] is None:
                return False
            current = current[char_code]
        return True

3. 最適化版（ネストされた辞書 + 終わりマーカー）

最もシンプルでパフォーマンスの良い方法の一つです。単一の辞書構造内に全てのデータを保持し、単語の終わりを特別なキー（例: '_end_'）でマークします。

class TrieV3:
    def __init__(self):
        self.root = {}

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node:
                node[char] = {}
            node = node[char]
        # 単語の終わりを示す特別なキーを追加
        node['_end_'] = True

    def search(self, word: str) -> bool:
        node = self.root
        for char in word:
            if char not in node:
                return False
            node = node[char]
        # 単語の終わりマーカーが存在するか確認
        return '_end_' in node

    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for char in prefix:
            if char not in node:
                return False
            node = node[char]
        return True

最適なアルゴリズム

ローカルでのベンチマークテストによると、**3番目の実装（ネストされた辞書を使用する TrieV3）**が最も高速でした。

この問題から得られる主な結論は以下の通りです。

• 独立した変数を辞書構造内に保存することで、独立した変数の数を減らし、パフォーマンスを向上させることができます。
• 大きなデータセットの事前初期化はメモリ使用量を増やし、パフォーマンスを低下させる可能性があります。必要なときにのみデータ構造を作成する方が効率的です。