Trieでのワイルドカードと正規表現検索
その深さにあるすべての子へ分岐することで'.'ワイルドカードの一致をサポートし、design-add-and-search-words-data-structure問題を解きます。
「Trieでのワイルドカードと正規表現検索」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
ワイルドカード検索の問題
標準的な trie の検索では、文字を完全一致させます。ワイルドカード検索では、任意の 1 文字に一致する特殊文字 '.' を追加します。検索中に '.' に遭遇した場合、特定の子を 1 つたどるのではなく、すべての子を試す必要があります。これを分岐（fan-out）と呼びます。これが、LeetCode 211 の「Design Add and Search Words Data Structure」の中心的な考え方です。各 '.' によって、そのレベルの子の数だけ検索パスが増えます。
再帰によるワイルドカード検索
再帰的な DFS ヘルパーを使ってワイルドカード検索を実装します。パターン内の各文字について、リテラル文字であれば対応する子をたどり（存在しなければ False を返します）、'.' であればすべての子に対して再帰呼び出しを行い、いずれかが成功した時点で True を返します。パターンの末尾に到達したら、node.is_end を返します。
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class WordDictionary:
def __init__(self):
self.root = TrieNode()
def addWord(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 search(self, word):
def dfs(node, i):
if i == len(word):
return node.is_end
c = word[i]
if c == '.':
return any(dfs(child, i+1) for child in node.children.values())
if c not in node.children:
return False
return dfs(node.children[c], i+1)
return dfs(self.root, 0)
wd = WordDictionary()
wd.addWord('bad')
wd.addWord('dad')
wd.addWord('mad')
print(wd.search('.ad')) # True
print(wd.search('b..')) # True
print(wd.search('pad')) # False分岐に any() を使う理由
'.' に遭遇したら、any(dfs(child, i+1) for child in node.children.values()) を呼び出します。any() のジェネレーターは短絡評価されるため、いずれかの子が True を返した時点で停止します。これにより、不要な探索を避けられます。最悪の場合（パターンがすべて '.' の場合）はすべてのパスを探索するため、計算量は O(26^k) です。ここで k はドットの数を表し、大規模な trie では '....' のようなパターンは高コストになります。
キューを使った反復的なワイルドカード検索
反復的な方法では、(node, index) のペアを格納するキューを使用します。最初に (root, 0) を入れます。各ペアについて、index == len(word) かつ node.is_end であれば True を返します。それ以外の場合は現在の文字を処理し、'.' ならすべての子をキューに追加し、リテラル文字なら一致する子だけを追加します。これは本質的には、trie のパスに対する BFS です。
from collections import deque
def search_iterative(root, word):
queue = deque([(root, 0)])
while queue:
node, i = queue.popleft()
if i == len(word):
if node.is_end:
return True
continue
c = word[i]
if c == '.':
for child in node.children.values():
queue.append((child, i+1))
elif c in node.children:
queue.append((node.children[c], i+1))
return False
print('Iterative BFS-based wildcard search')ワイルドカード検索の計算量分析
ワイルドカードを含まないパターンでは、検索の計算量は O(m) です。k 個のワイルドカードを含むパターンでは、最悪の場合 O(26^k × m) となり、ワイルドカードの数に対して指数関数的に増加します。実際には、ワイルドカードは通常まばらで、trie も浅いため、性能は許容範囲に収まります。すべてがワイルドカードのパターン（たとえば、長さ k のすべての単語に一致するパターン）では、trie 全体の走査に退化します。
1 文字ワイルドカードを超えた正規表現検索
完全な正規表現（たとえば、0 文字以上に一致する '*'）に拡張するには、別の処理が必要です。'*' は任意のサフィックスに一致できるため、これに遭遇した場合は、現在のノードから続くすべての trie パスを試す必要があります。trie で真の正規表現マッチングを行うのは複雑で、通常は NFA/DFA の構成で扱います。面接では、1 文字ワイルドカード（'.'）が標準的なパターンです。
Glob パターンマッチング
'?'（任意の 1 文字）と '*'（空を含む任意の文字列）を使ったGlob マッチングは、DP で実装できます。trie で実装する場合、'?' は 1 レベルの分岐（'.' と同様）に対応し、'*' は複数レベルの DFS に対応します。組み合わせた DP では、dp[i][j] は pattern[0..i] が string[0..j] に一致する場合に True となります。面接官は通常、どの種類を実装するかを指定します。
実践例: IP アドレスルーティング
ワイルドカード trie は、IP ルーティングテーブルで使用されます。ここでは '*' がプレフィックスのワイルドカードとして機能します。ルーターは '192.168.*' のようなルートプレフィックスを保存し、受信したアドレスと照合します。最長プレフィックスマッチ（最も具体的なルートを優先する仕組み）は、trie を可能な限り深くたどり、最後に一致した位置を使用して実装します。これは、trie のプレフィックス操作とワイルドカード操作の実世界における応用例です。
最適化: デッドブランチの枝刈り
trie のノードに子がなく（リーフで）、is_end = False の場合、そのノードに到達する検索は必ず False になります。ワイルドカード検索では、再帰呼び出しの前にこのような行き止まりのノードをスキップすることで、不要な呼び出しを枝刈りできます。各ノードで word_count（そのサブツリーに含まれる単語の総数）を管理すると、残りのパターン長の制約に一致する単語がないサブツリー全体をスキップできます。
WordDictionary クラス完全版（面接対応）
insert とドットワイルドカード検索を 1 つのクラスにまとめた、簡潔で面接に対応できる WordDictionary です。これは LeetCode 211 で想定される実装そのものです。短絡評価される any() を使った再帰検索は簡潔で、面接官に分岐のロジックを明確に示せます。
class WordDictionary:
def __init__(self):
self.root = {}
def addWord(self, word):
node = self.root
for c in word:
node = node.setdefault(c, {})
node['#'] = True
def search(self, word):
def dfs(node, i):
if i == len(word):
return '#' in node
if word[i] == '.':
return any(dfs(v, i+1) for k, v in node.items() if k != '#')
nxt = node.get(word[i])
return dfs(nxt, i+1) if nxt is not None else False
return dfs(self.root, 0)
wd = WordDictionary()
for w in ['at','and','an','add']:
wd.addWord(w)
print(wd.search('a.')) # True (at, an)
print(wd.search('.nd')) # True (and)
print(wd.search('...')) # True (and, add)
print(wd.search('x.')) # Falsesetdefault を使った簡潔な trie
dict.setdefault(key, default) は、key が存在すればその値を返し、存在しなければ default を挿入して返します。insert で node.setdefault(c, {}) を使うと、if-else によるチェックを省略できます。子の辞書がなければ作成し、どちらの場合でもその辞書を返します。これにより、insert は 1 行の走査になります。for c in word: node = node.setdefault(c, {})。簡潔で Python らしい書き方です。
理解度チェック
このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、ワイルドカード '.' では、一致する位置ですべての子に分岐する必要があり、再帰的な DFS を使うこと、ジェネレーターとともに any() を使うと短絡評価によって早期終了できること、そしてsetdefault によって trie への挿入を簡潔な 1 行で記述できることを学びました。次は trie とバックトラッキングを組み合わせ、2D ボード上から複数の単語を同時に見つける Word Search II を解きます。
よくある質問
「Trieでのワイルドカードと正規表現検索」レッスンは無料ですか？
はい。「Trieでのワイルドカードと正規表現検索」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「Trieでのワイルドカードと正規表現検索」で何を学びますか？
その深さにあるすべての子へ分岐することで'.'ワイルドカードの一致をサポートし、design-add-and-search-words-data-structure問題を解きます。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。
「Trieでのワイルドカードと正規表現検索」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- TrieNodeクラス：挿入と検索
- Prefix SearchとStarts-With
- Trieでのワイルドカードと正規表現検索
- Word Search II：Trie＋グリッド上のバックトラッキング