Implement Trie (Prefix Tree)
トライ（プレフィックス木）は、単語の先頭に関する判定を高速に行えるように単語を格納します。小文字の単語を対象に、次の3つの操作を実装してください。insert wは単語wを追加し、search wはw自体が挿入されているかどうかを判定し、startsWith pは挿入された単語のいずれかがpで始まるかどうかを判定します。単語はそれ自体のプレフィックスでもあります。
操作は順番にopsとして与えられ、words[i]はops[i]に対応する単語またはプレフィックスです。空の状態で始まる1つのトライに対して操作を実行し、各操作につき1つの文字列を返してください。挿入の場合は"null"、検索またはstartsWithの場合は"true"または"false"を返します。
関数
- opsstring-array
- 実行される順序での演算
- wordsstring-array
- 各操作を表す語または接頭辞
- 戻り値string-array
- 操作ごとに1つの回答をテキストとして
制約
1 ≤ ops.length ≤ 2000words.length == ops.length- すべての
ops[i]は、insert、search、またはstartsWithです。 1 ≤ words[i].length ≤ 20words[i]には小文字の英字のみが含まれています。
例
- 入力
- ops = ["insert", "search", "startsWith", "insert", "search"]words = ["card", "car", "car", "car", "car"]
- 出力
- ["null", "false", "true", "null", "true"]
- 説明
- 最初に格納されているのは
cardだけなので、carを検索すると"false"が返されます。単語として挿入されたことはないからです。これはcardの先頭部分なので、startsWith carは"true"を返します。carが挿入されると、検索で見つかります。
- 入力
- ops = ["insert", "insert", "startsWith", "search", "startsWith", "search", "startsWith"]words = ["tea", "ten", "te", "te", "tex", "ten", "tea"]
- 出力
- ["null", "null", "true", "false", "false", "true", "true"]
- 説明
- どちらの単語も
teで始まるため、startsWith teは"true"ですが、teと完全に一致する単語はないため、検索は失敗します。texで始まる単語はありません。tenが挿入され、teaはそれ自身の接頭辞なので、最後の2つの答えは"true"です。
- 入力
- ops = ["search", "startsWith", "insert", "search", "startsWith", "startsWith"]words = ["dog", "d", "dog", "dog", "dogs", "do"]
- 出力
- ["false", "false", "null", "true", "false", "true"]
- 説明
- トライ木は空の状態で始まるため、最初の2つの答えは
"false"です。dogが挿入されると、検索で見つかり、dogsで始まる単語はなく、doはdogの先頭部分です。
提出時に隠しテスト+16件
発展問題
異なる保存済み単語のうち、pで始まるものの数をO(L)時間で返すcountPrefix p操作を、どのように追加しますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
単語全体の集合なら、
searchに対して1回の検索で答えられますが、すべての単語を1つずつ確認しないと、teで始まる単語があるかどうかはわかりません。同じ始まり方をする単語が、その始まりの部分の記憶領域を共有するとしたらどうでしょう？各ノードが接頭辞を表し、次に続く可能性のある各文字に対して子ノードへのリンクを1つ持つ木を構築します。単語はルートからの経路になります。各ノードに、保存された単語がそのノードでちょうど終わるかどうかを示すフラグを付けます。
すべての操作は、ルートから各文字をたどります。
insertは存在しないノードを作成し、最後のノードにフラグを設定します。startsWithは、たどり終えた時点で成功します。searchでは、停止したノードにフラグが設定されていることも必要です。
解説
ハッシュセットはsearchにすぐ答えられますが、startsWithは特定の文字列で始まるすべての単語について尋ねるものであり、セットには始まりという概念がありません。トライはその始まり自体を格納します。すべての単語はルートから文字をたどる経路であり、同じ始まりの単語は経路の先頭を共有し、ノード上のフラグは格納された単語の終わりを示します。すると、どちらの問いにも、格納されている単語の数にかかわらず、最大でもL個のリンクをたどるだけで答えられます。ここでLはクエリの長さです。
単語のリストを保持して、それをスキャンする
考え方
挿入された単語はすべてリストに保存します。search wでは、wを保存されている各単語と比較します。startsWith pでは、保存されている単語の中にpで始まるものがあるかどうかを確認します。2つ目の例では、startsWith teは最初にteaを調べ、そこで停止します。一方、startsWith texは、"false"と答える前に両方の単語を調べる必要があります。
これは正しく、この場合の制限の範囲内では処理も完了しますが、クエリのたびに保存されているすべての単語を調べます。n個の単語が保存されている場合、クエリごとに最大L文字の比較をn回行うことになります。保存された単語が1,000個、クエリが1,000件なら、文字列の比較は100万回になり、辞書が大きくなるにつれて処理量も増え続けます。また、何も共有されません。teaとtenは、それぞれ独自にtとeを保存します。
アルゴリズム
- 空の単語リストから始めます。
insert wの場合：リストにwを追加します。search wの場合：保存されている単語の中にwと等しいものがあるかどうかを返します。startsWith pの場合：保存されている単語の中にpで始まるものがあるかどうかを返します。- 各回答をテキストとして記録し、リストを返します。
def trieOps(ops, words):
stored = []
result = []
for op, word in zip(ops, words):
if op == "insert":
stored.append(word)
result.append("null")
elif op == "search":
found = any(s == word for s in stored)
result.append("true" if found else "false")
else:
found = any(s.startswith(word) for s in stored)
result.append("true" if found else "false")
return resultA trie：子ノードへのリンクと終端フラグ
考え方
トライの各ノードは、1つの接頭辞を表します。つまり、ルートからそのノードまでの経路上にある文字列です。ルートは空の接頭辞を表します。ノードには2つのものが格納されます。次に続く各文字に対応する子リンク（26個のスロットを持つ配列、または文字からノードへのマップ）と、格納された単語がこのノードでちょうど終わるかどうかを示すフラグ isEnd です。
insert はルートから単語をたどります。各文字について子リンクをたどり、リンクがなければ先にノードを作成します。そして最後の文字で isEnd を設定します。2つ目の例では、tea を挿入すると t、te、tea のノードが作成され、tea に印が付きます。ten を挿入すると t と te を再利用し、ten だけを追加します。この2つの単語は te までの経路を共有します。これが、このデータ構造が接頭辞木と呼ばれる理由です。
search と startsWith は、何も作成せずに同じようにたどります。リンクがなければ、その文字列で始まる格納済みの単語はないため、どちらも false を返します。tex は te のノードで止まります。このノードには x へのリンクがありません。最後までたどり着くと、そのノードが調べたい接頭辞に当たります。startsWith は true を返し、search はそのノードのフラグの値を返します。te のノードは存在しますが、そこを通る単語はさらに下のノードで終わるため、フラグはオフです。したがって、startsWith te は true、search te は false です。
単語と接頭辞を区別するのがこのフラグです。最初の例では、card を挿入すると、c、a、r の経路ができます。フラグがなければ、search car は誤って true を返してしまいます。後から car を挿入してもノードはまったく作られず、フラグがオンになるだけです。
各操作がたどるリンクは最大でも L 個です。ここで L は単語の長さなので、格納されている単語数にかかわらず、計算量は O(L) です。トライが保持するノードは異なる接頭辞ごとに1つで、挿入された文字の総数を超えることはありません。
アルゴリズム
- 子へのリンク（26 個のスロットまたはマップ）と
isEndフラグを持つノードを定義し、空のルートを作成します。 insert wの場合：ルートから始めて、wの各文字に対応するリンクをたどり、リンクがない場合はノードを作成します。最後のノードにisEndを設定します。- ヘルパー関数
find(p)を記述します：ルートから始めて、pの各文字に対応するリンクをたどり、リンクが見つからなければすぐに中止します。たどり着いたノードを返します。 search wの場合：find(w)がisEndが設定されたノードにたどり着いたとき、true と答えます。startsWith pの場合：find(p)がノードにたどり着いたとき、true と答えます。- 操作を順番に実行し、それぞれについて
"null"、"true"または"false"を記録します。
class TrieNode:
def __init__(self):
self.children = {} # letter -> TrieNode
self.is_end = False # does a stored word end at this node?
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True
def _find(self, prefix):
# Follow the letters from the root; None as soon as a link is missing.
node = self.root
for ch in prefix:
node = node.children.get(ch)
if node is None:
return None
return node
def search(self, word):
node = self._find(word)
return node is not None and node.is_end
def starts_with(self, prefix):
return self._find(prefix) is not None
def trieOps(ops, words):
trie = Trie()
result = []
for op, word in zip(ops, words):
if op == "insert":
trie.insert(word)
result.append("null")
elif op == "search":
result.append("true" if trie.search(word) else "false")
else:
result.append("true" if trie.starts_with(word) else "false")
return result
落とし穴と境界ケース
バグの多くは、「単語がここで終わる」ことと「単語がここを通過する」ことを混同することで発生します。
- 経路が存在するときは常に
searchがtrueを返すようにしてしまう。cardを挿入するとcarの経路は存在しますが、carは挿入されていません。 - 新しく作成したノードにだけ
isEndを設定してしまう。cardsの後にcardを挿入しても何も作成されませんが、最後のノードにはフラグが必要です。 - リンクがすでに存在する場合でも、新しい子ノードを作成してしまう。すると、その下に格納されているものがすべて失われます。たとえば、新しい
tノードを使ってtenを挿入すると、teaが失われます。 - 単語はそれ自体の接頭辞でもあることを忘れてしまう。
teaを挿入した後は、startsWith teaはtrueです。 - 経路の終端を越えて読み進めてしまう。格納されているすべての単語より長い接頭辞、たとえば
sunだけが格納されている場合のsunnyは、最初に見つからないリンクで停止し、falseを返す必要があります。 - 戻り値をbooleanにしたり、回答から挿入操作を除外したりしてしまう。挿入操作の
"null"も含め、すべての操作に1つの文字列が対応します。
よくある質問4
トライ木の時間計算量はどのくらいですか？
Insert、search、startsWith はそれぞれ、引数の各文字につき1つのリンクをたどるため、長さ L の単語に対していずれも O(L) 時間がかかり、格納されている単語の数には左右されません。トライには挿入された文字ごとに最大1つのノードがあるため、合計 T 文字を挿入した場合、空間計算量は O(T) 個のノードとなり、各ノードには最大26個の子リンクが格納されます。
ハッシュセットではなくトライを使う理由は何ですか？
ハッシュセットは単語全体の検索にO(L)で答えられますが、すべての単語を走査しないと接頭辞に関する質問には答えられません。すべての単語のすべての接頭辞を保持する2つ目のセットを追加する方法もありますが、20文字の単語では20個の接頭辞が保存され、その間に合計210文字が必要になります。トライは共有する接頭辞を一度だけ保存し、同じ探索でどちらの質問にも答えます。各ノードに26個の配列スロットがあるため、接頭辞の下を探索すると単語が文字順に並びます。これはオートコンプリートに必要です。
トライのノードには、26個のリンクを持つ配列とハッシュマップのどちらを使うべきでしょうか？
配列を使うと、文字ごとに1つのインデックスで子ノードを最速で検索できますが、各ノードは1つしか使わない場合でも26個分の領域を消費します。マップは存在する子ノードだけを格納し、どのようなアルファベットにも対応しますが、文字ごとにハッシュ計算が必要です。英小文字の単語であればどちらでも問題ありませんが、Unicodeテキストや疎なトライ木では、マップを使うとメモリを大幅に節約できます。
トライ木は実際にどこで使われていますか？
自動補完や検索候補では、トライを入力された接頭辞までたどり、その下にある単語を一覧表示します。スペルチェッカー、盤面から辞書に載っている単語を探すワードゲーム、最長一致するアドレスの接頭辞を見つけるルーターも、同じ構造を使います。多くの文字列が同じ先頭部分を共有し、その先頭部分で検索する場合は、トライが適しています。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def trieOps(ops, words):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
ops = ["insert", "search", "startsWith", "insert", "search"] words = ["card", "car", "car", "car", "car"]
期待値
["null", "false", "true", "null", "true"]