Implement Trie (Prefix Tree)
小文字の単語を扱うトライ（プレフィックスツリー）を作成し、3つの操作を実装します。insert w は単語 w を追加し、search w は w 自体が追加済みかどうかを判定し、startsWith p は追加済みの単語のうち p で始まるものがあるかどうかを判定します。単語はそれ自身のプレフィックスでもあります。
操作 i は、words[i] に対する ops[i] です。空のトライに対して順番に実行し、それぞれ1つの文字列を返します。insert の場合は "null"、search または 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"]
- 説明
carはcardで始まるので、startsWith carは"true"ですが、carは挿入されていないため、最初の検索結果は"false"です。insert 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で始まりますが、どちらも正確にはteではないため、startsWith は"true"で、search は"false"です。texで始まる単語はなく、teaはそれ自体の接頭辞です。
- 入力
- ops = ["search", "startsWith", "insert", "search", "startsWith", "startsWith"]words = ["dog", "d", "dog", "dog", "dogs", "do"]
- 出力
- ["false", "false", "null", "true", "false", "true"]
- 説明
- 空のトライでは、どちらのクエリも
"false"です。insert dogの後、検索で見つかり、dogsで始まる単語はなく、doはdogで始まります。
発展問題
引き続き O(L) 時間で、p で始まる保存済みの異なる単語の数を返す countPrefix p 操作を追加するには、どうすればよいでしょうか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
単語全体の集合なら、1回の検索で
searchに答えられますが、1つずつ確認しないと、どの単語がteで始まるかは分かりません。同じ始まり方をする単語同士で、その始まりの部分の保存領域を共有できたらどうでしょうか？各ノードが接頭辞を表し、次に続く可能性のある各文字に対して子ノードへのリンクを1つ持つ木を作ります。すると、単語はルートからのパスになります。保存された単語がちょうどその位置で終わるかどうかを示すフラグを、各ノードに付けます。
各操作はルートから文字をたどります。
insertは存在しないノードを作成し、最後のノードにフラグを設定します。startsWithはたどった先が末尾に達すると成功しますが、searchでは停止したノードにフラグが設定されていることも必要です。
解説
ハッシュ集合ならsearchには答えられますが、先頭という概念がないため、startsWithではすべての単語を走査することになります。トライでは、各単語をルートから文字をたどる経路として格納します。同じ文字で始まる単語は経路の一部を共有し、フラグで格納された単語の終わりを示します。どちらのクエリも、最大L個のリンクをたどるだけで済みます。
単語のリストを保持して、それをスキャンする
考え方
追加した単語はすべてリストに保持します。search wはwを保存されている各単語と比較し、startsWith pは保存されている単語のいずれかがpで始まるかどうかを確認します。定義を直接検証するため、これは正しい方法です。保存されている単語がn個ある場合、各クエリでは最大L文字の比較を最大n回行います。単語が1,000個、クエリが1,000回なら、文字列比較は100万回になります。
アルゴリズム
- 空のリストから始めます。
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 resultトライ：子ノードへのリンクと終端フラグ
考え方
各ノードは1つの接頭辞、つまりルートからそのノードまでの経路上の文字を表します。次に続く可能性のある各文字に対応する子ノードへのリンク（26個のスロットまたはマップ）と、保存された単語がそこでちょうど終わるかどうかを示すフラグisEndを持ちます。teaを挿入すると、t、te、teaのノードが作成されます。その後tenを挿入すると、2つの単語がteまでの経路を共有しているため、追加されるのはtenだけです。
リンクが見つからない経路は、その文字列で始まる保存済みの単語がないことを示します。texの場合、xへのリンクがないためteで止まります。末尾まで到達する経路は、検索語に対応するノードにたどり着くため、startsWithはtrueとなり、searchはフラグに応じて答えます。teのノードは存在しますが、フラグはオフなので、search teはfalseです。保存されている単語の数にかかわらず、各操作がたどるリンクは最大でもL個で、トライには異なる接頭辞ごとに1つのノードが格納されます。
アルゴリズム
- 子リンクを持たず、
isEndがオフのルートを作成します。 insert w：ルートから、各文字のリンクをたどり、リンクがない場合はノードを作成します。最後のノードでisEndをオンにします。find(p)：ルートから、各文字のリンクをたどります。リンクがない場合はその時点で何も返さず、そうでなければ到達したノードを返します。search w：find(w)がisEndが設定されたノードを返す場合、true です。startsWith p：find(p)がノードを返す場合、true です。
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を返すようにすること。insert cardの後、carのパスは存在しますが、search carはfalseでなければなりません。 - 新しく作成されたノードにだけ
isEndを設定すること。cardsの後にcardを挿入しても何も作成されませんが、最後のノードにはフラグが必要です。 - リンクがすでに存在する場合に、新しい子ノードを作成すること。新しい
tノードを使ってtenを挿入すると、teaが失われます。 - パスの終端を越えて読み進めること。
sunだけが格納された状態でstartsWith sunnyを実行した場合、最初にリンクが見つからない時点で停止し、falseを返さなければなりません。
よくある質問3
トライの時間計算量はどれくらいですか？
挿入、検索、startsWithはいずれも文字ごとに1つのリンクをたどるため、単語の長さがLの場合、格納されている単語の数にかかわらず、それぞれO(L)かかります。空間計算量は、合計T文字を挿入した場合、最大26個の子リンクを持つノードO(T)個分です。
ハッシュセットではなくトライを使うのはなぜですか？
ハッシュセットでは単語全体を O(L) で検索できますが、すべての単語を走査しないと、接頭辞に関する質問には答えられません。すべての接頭辞を別のセットに保存すると、20文字の単語1つにつき210文字分のコストがかかります。トライでは共通の接頭辞を一度だけ保存し、1回の走査で両方の質問に答えられます。
トライのノードには、26個のリンクを持つ配列とハッシュマップのどちらを使うべきでしょうか？
配列ではインデックス1つで子を見つけられますが、子が1つしかないノードでもノードごとに26個のスロットを必要とします。マップは存在する子だけを格納し、任意のアルファベットに対応しますが、文字ごとにハッシュのコストがかかります。英小文字の場合はどちらでも使えますが、Unicodeや疎なトライではマップを使うとメモリを節約できます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def trieOps(ops, words):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
ops = ["insert", "search", "startsWith", "insert", "search"] words = ["card", "car", "car", "car", "car"]
期待される出力
["null", "false", "true", "null", "true"]