トライ
01 / 一文での本質
文字列の集合を文字の木に格納する — 各ノードは接頭辞、 各辺は 1 文字、そして特別な単語終端マーカーが「この接頭辞自体が保存された単語」と 「これはより長い単語へ向かう途中の単なる接頭辞」を区別する。
問題接頭辞木に単語を保存し検索する操作数7内訳挿入 4 · 検索 3
空のトライ — ルートのみ。各操作は 1 文字ずつ木をたどる。
ステップ
0 / 35
操作
—
ノード数
1
直近の結果
—
0 / 35
02 / パターンの骨格
# トライのノード = マップ + 「これは単語の終端か」フラグclass Node:children: dict[char, Node] = {}is_end: bool = False def insert(word):node = rootfor ch in word:if ch not in node.children:node.children[ch] = Node()node = node.children[ch]node.is_end = True def search(word):node = walk(word) # 1 文字ずつ辿る。外れたら None を返すreturn node is not None and node.is_end
03 / このパターンを使うべき合図
「接頭辞クエリ」
問題が気にしているのは完全一致ではなく接頭辞 — オートコンプリート、最長共通接頭辞、「X で始まる単語をすべて」。 こうしたクエリにハッシュ集合では線形走査より良い答えは出せない。
「単語辞書」
固定の辞書を何度もクエリするケース。辞書がトライ本体、クエリは木の上のたどり方。 構築コストはすべてのクエリに償却される。
「アルファベットが有界なキー」
各ステップは小さく固定された値のうち 1 つに分岐する — 小文字(26)、数字(10)、IP オクテット(256)。 アルファベットが無限あるいは連続なら、別の構造の方が向いている。
「構造の共有」
"car"、"card"、"care"、"cart" のような単語は最初の 3 ノードを共有する — トライはその接頭辞を一度だけ保持する。 ほとんどの単語が接頭辞を共有しないなら、トライはハッシュ集合の薄いラッパーになり、利得は小さくなる。04 / よくある落とし穴
i.
単語終端マーカーを忘れる。
検索語の最後の文字に到達するだけでは足りない — そのノードが
is_end として マークされている必要がある。マーカーを省くと、"cat" を挿入した後の search("ca") も成功してしまう、これは誤り。このマーカーこそが、接頭辞木を単語集合に変えるもの。ii.
search と startsWith を取り違える。
search(w) は終端ノードにマーカーがあることを要求する。 startsWith(p) はたどり切れることだけを要求する — 終端チェックはしない。 木をたどるコードは共通で、事後条件が 1 行だけ違う。iii.
キーが有界でないのに 26 スロット配列を使う。
固定長の
children[26] は小文字限定のアルファベットに対して高速かつキャッシュに優しいが、 より大きなアルファベット(Unicode、バイト列)ではメモリの大惨事になる。 既定はハッシュマップ。アルファベットが小さく内側ループがホットなときだけ固定配列に切り替える。05 / LeetCode で練習
ファミリーから 4 問。最初の 1 問は定番の「データ構造を実装する」課題。 次の 2 問はそこに機能を足す(ワイルドカード、盤面上のマルチワード探索)。 4 問目はクエリの向きを反転させる:辞書を与え、特定の構造的性質を持つ最長の単語を見つける。