Prefix SearchとStarts-With
挿入済みの単語に指定した接頭辞を共有するものがあればtrueを返すstarts_withメソッドを追加し、自動補完候補の生成に利用します。
「Prefix SearchとStarts-With」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
プレフィックスクエリの威力
ハッシュマップに対するTrieの決定的な利点は、効率的なプレフィックス検索です。プレフィックスクエリでは、「このプレフィックスで始まる格納済みの単語はいくつあるか」「このプレフィックスを持つ格納済みの単語はすべて何か」「このプレフィックスを持つ単語が存在するか」といった問いに答えられます。これらのクエリは、格納されている単語の総数に依存せず、プレフィックスの長さをpとしてO(p)で実行できます。そのため、Trieはオートコンプリートや検索候補に適しています。
starts_withメソッド
starts_with(prefix)は、格納されている単語のいずれかが指定されたプレフィックスで始まる場合にTrueを返します。プレフィックスの各文字に従ってTrieを走査します。欠落した辺に遭遇せずにすべての文字をたどれれば、そのプレフィックスは存在し、少なくとも1つの単語がそのプレフィックスで始まります。実装はsearchと同じですが、走査を終えた時点ですぐにTrueを返し、is_endは確認しません。
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
def starts_with(self, prefix):
node = self.root
for c in prefix:
if c not in node.children:
return False
node = node.children[c]
return True
t = Trie()
for w in ['hello','help','world','word']:
t.insert(w)
print(t.starts_with('hel')) # True
print(t.starts_with('wor')) # True
print(t.starts_with('xyz')) # Falseプレフィックスを持つすべての単語のオートコンプリート
オートコンプリートを実装するには、まずプレフィックスの終端ノードまで走査し、次にそのノードからDFS（またはBFS）を行って、そこから分岐するすべての単語を集めます。集めた各サフィックスの先頭にプレフィックスを付けて、完全な単語を復元します。これは、pをプレフィックスの長さ、Wを一致する単語すべての文字数の合計とすると、O(p + W)の操作です。
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
def autocomplete(self, prefix):
node = self.root
for c in prefix:
if c not in node.children:
return []
node = node.children[c]
# DFS from prefix end node
results = []
def dfs(n, path):
if n.is_end:
results.append(prefix + path)
for char, child in n.children.items():
dfs(child, path + char)
dfs(node, '')
return results
t = Trie()
for w in ['apple','app','application','apply','apt']:
t.insert(w)
print(t.autocomplete('app')) # ['app','apple','apply','application']ソート済みの候補を返す
ソート済みのオートコンプリートを実現するには、DFS中に子ノードをアルファベット順で走査します（sorted(node.children.items())を反復します）。これによりO(ALPHABET_SIZE × depth)のオーバーヘッドが加わりますが、辞書順に並んだ結果が保証されます。配列ベースのTrieでは、インデックス0〜25が順序付けられているため、子ノードは常にアルファベット順に走査されます。
def dfs_sorted(node, prefix, results):
if node.is_end:
results.append(prefix)
for char in sorted(node.children.keys()): # alphabetical order
dfs_sorted(node.children[char], prefix + char, results)
print('Iterating children in sorted order gives lex-sorted suggestions')トップKのオートコンプリート候補
頻度による上位k件の候補を取得するには、各ノードに、そのノードで終わる単語が検索された回数を保持するcountを追加します。候補を集める際は、サイズkの最大ヒープを使用します。これにより、DFSで得られるO(W)の結果集合を、すべての一致結果を実体化せずにO(k)へ削減できます。実際の検索エンジンでは、Trieによるプレフィックス走査と頻度データを組み合わせて、高速で関連性の高い候補を提示します。
LeetCode 208向けTrieの実装
LeetCode 208の「Implement Trie (Prefix Tree)」では、insert(word)、完全一致のブール値を返すsearch(word)、プレフィックス一致のブール値を返すstartsWith(prefix)の3つを実装します。これは標準的なTrie実装です。searchにはis_end=Trueが必要ですが、startsWithにはプレフィックスの経路が存在することだけが必要です。
class Trie:
def __init__(self):
self.root = {}
def insert(self, word):
node = self.root
for c in word:
if c not in node:
node[c] = {}
node = node[c]
node['#'] = True # '#' marks word end
def search(self, word):
node = self.root
for c in word:
if c not in node: return False
node = node[c]
return '#' in node
def startsWith(self, prefix):
node = self.root
for c in prefix:
if c not in node: return False
node = node[c]
return True
t = Trie()
t.insert('apple')
print(t.search('apple')) # True
print(t.search('app')) # False
print(t.startsWith('app')) # True終端マーカーとして「#」を使用する（Dict Trie）
Trieをネストした辞書として表し、'#'のような特別な番兵キーで単語の終端を示すと、TrieNodeクラスが不要になる便利な方法があります。これは簡潔で面接にも向いていますが、明示的なTrieNodeオブジェクトを使う方法より少し読みづらくなります。どちらの実装も使用できます。時間制限がある場合は、辞書版のほうが素早く記述できます。
Trieを使った最長共通プレフィックス
文字列のリストの最長共通プレフィックスを見つけるには、すべての文字列をTrieに挿入し、ルートから、次の条件を満たす限り1つだけ存在する経路をたどります。(1) 現在のノードが子をちょうど1つ持つこと。(2) is_endがFalseであること。どちらかの条件が崩れたら停止します。たどった経路が最長共通プレフィックスです。
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
def longest_common_prefix(words):
root = TrieNode()
for word in words:
node = root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
prefix = []
node = root
while len(node.children) == 1 and not node.is_end:
char, node = next(iter(node.children.items()))
prefix.append(char)
return ''.join(prefix)
print(longest_common_prefix(['flower','flow','flight'])) # 'fl'
print(longest_common_prefix(['dog','racecar','car'])) # ''Replace Words問題
Replace Words（LeetCode 648）は、語根の辞書と文が与えられたとき、文中の各単語を辞書内で一致する最短の語根に置き換える問題です。すべての語根をTrieに挿入します。文中の各単語について、語根の終端が見つかるまでTrieを走査し、その語根を置換結果として返します。一致する語根がなければ、元の単語をそのまま使用します。総文字数に対してO(total chars)で実行でき、O(n × m)の全探索より効率的です。
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
def replaceWords(dictionary, sentence):
root = TrieNode()
for word in dictionary:
node = root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
def find_root(word):
node = root
for i, c in enumerate(word):
if c not in node.children: break
node = node.children[c]
if node.is_end:
return word[:i+1]
return word
return ' '.join(find_root(w) for w in sentence.split())
print(replaceWords(['cat','bat','rat'], 'the cattle was rattled by the battery'))Map Sum Pairs問題
Map Sum（LeetCode 677）は、キーと値のペアを挿入し、指定されたプレフィックスを持つキーの値の合計を返す問題です。各TrieNodeにvalフィールドを追加します。挿入では終端まで走査して値を設定し、合計クエリではプレフィックスの終端ノードまで走査して、その下にあるすべてのvalフィールドをDFSで合計します。別の方法として、挿入時に各ノードへ累積合計を格納すれば、O(p)のクエリを実現できます。
結果数を制限した autocomplete の実装
本番環境の autocomplete システムでは、プレフィックスに一致する単語が数千個ある場合、すべての単語を返すのは現実的ではありません。代わりに、DFS の走査中にサイズ k の max-heapを使用し、それまでに見つかったスコア上位 k 個の単語を保持します。上位 k 個に入る単語が存在する可能性のない DFS の分岐は、早い段階で停止します（スコアの上限による枝刈り）。これにより、k 個の候補に対するクエリごとの計算量は O(p + k × log k) となり、一致する単語をすべて収集する場合より大幅に効率的です。
理解度チェック
このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、starts_with はプレフィックスのパスを走査し、そのパスが存在すれば True を返すため、is_end のチェックは不要であること、autocomplete の DFS は、プレフィックスの終端ノードから文字を追加しながら下降して、すべての単語を収集すること、そしてノードにカウントや値を追加すると、合計値のクエリや上位 k 件の候補取得が可能になることを学びました。次は、trie にワイルドカードと正規表現のマッチングを追加します。
よくある質問
「Prefix SearchとStarts-With」レッスンは無料ですか？
はい。「Prefix SearchとStarts-With」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「Prefix SearchとStarts-With」で何を学びますか？
挿入済みの単語に指定した接頭辞を共有するものがあればtrueを返すstarts_withメソッドを追加し、自動補完候補の生成に利用します。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。
「Prefix SearchとStarts-With」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- TrieNodeクラス：挿入と検索
- Prefix SearchとStarts-With
- Trieでのワイルドカードと正規表現検索
- Word Search II：Trie＋グリッド上のバックトラッキング