Word Search II：Trie＋グリッド上のバックトラッキング
すべての対象単語をtrieに挿入し、2D盤面上でDFSバックトラッキングを実行して、O(m × n × 4^L)で有効な単語をすべて同時に見つけます。
「Word Search II：Trie＋グリッド上のバックトラッキング」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
Word Search II の問題
Word Search II（LeetCode 212）では、m × n の文字ボードと単語のリストが与えられます。各セルは 1 回しか使用できないという条件のもと、水平方向または垂直方向に隣接するセルを順番にたどって作れるすべての単語を見つけます。これは、単一の単語を扱う Word Search I より難しい問題です。すべての一致する単語を同時に見つける必要があり、単純に各単語に対して Word Search I を実行すると O(W × m × n × 4^L) となり、遅すぎます。
なぜ trie とバックトラッキングを組み合わせるのか
対象となるすべての単語をtrieに挿入し、その後ボード上で DFS によるバックトラッキングを実行すると、すべての単語を同時に検索できます。各ボードセルで、「このパスは対象の単語を表しているか」を確認する代わりに、「このパスは trie 内のプレフィックスと一致しているか」を確認します。trie のプレフィックスと一致しなくなった時点で DFS の分岐全体を枝刈りできるため、そのプレフィックスを共有するすべての単語について重複した処理を避けられます。
単語リストから trie を構築する
すべての単語を trie に挿入します。単なる boolean ではなく、リーフノードの node.word に完全な単語を保存します。こうすると、バックトラッキング中に完全一致が見つかったとき、文字を 1 つずつ再構築せずに、すぐ結果へ単語を追加できます。
class TrieNode:
def __init__(self):
self.children = {}
self.word = None # stores the complete word if this is an end node
def build_trie(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.word = word # mark complete word here
return root
root = build_trie(['eat','oath','ot'])
print('Trie built with', len(root.children), 'root children')グリッド上の DFS バックトラッキング
ボード上のすべてのセルから DFS を開始します。各ステップでは、(1) 現在のセルの文字が現在の trie ノードの子として存在するか確認し、(2) 存在すればセルを訪問済みとしてマークし（'#' のようなセンチネルに置き換え）、4 つの近傍へ再帰し、(3) 再帰処理の後にセルを元に戻します。trie ノードの word が None でない場合は結果に追加し、重複を避けるため None に設定します。
class TrieNode:
def __init__(self):
self.children = {}
self.word = None
def findWords(board, 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.word = word
m, n = len(board), len(board[0])
result = []
def dfs(i, j, node):
c = board[i][j]
if c not in node.children:
return
next_node = node.children[c]
if next_node.word:
result.append(next_node.word)
next_node.word = None # avoid duplicates
board[i][j] = '#' # mark visited
for di, dj in [(-1,0),(1,0),(0,-1),(0,1)]:
ni, nj = i+di, j+dj
if 0<=ni<m and 0<=nj<n and board[ni][nj] != '#':
dfs(ni, nj, next_node)
board[i][j] = c # restore
for i in range(m):
for j in range(n):
dfs(i, j, root)
return result
board = [['o','a','a','n'],['e','t','a','e'],['i','h','k','r'],['i','f','l','v']]
words = ['oath','pea','eat','rain']
print(findWords(board, words)) # ['oath','eat']計算量分析
時間計算量は、L を単語の最大長とするとO(m × n × 4^L)です。m×n 個の各開始セルについて、DFS は最大で 4^L 個のパスを探索します。trie によってどの単語のプレフィックスにも一致しないパスが枝刈りされるため、実際にははるかに高速です。trie の構築には、W を単語数とすると O(W × L) かかります。空間計算量は、trie に O(W × L)、再帰スタックの深さに O(L) です。
枝刈り: 見つけた後にリーフノードを削除する
単語を見つけた後、そのノードに子がなければ、単語を無効化するだけでなく、trie からリーフノードを削除します。これにより、後続の DFS 呼び出しで不要になった分岐を再訪するのを防げます。単語を見つけた後にノードの子が空になった場合は、そのノードを親の children dict から削除します。この最適化は、多くの単語が長いプレフィックスを共有している場合に特に効果的です。
def dfs_with_pruning(i, j, node, board, m, n, result):
c = board[i][j]
if c not in node.children:
return
next_node = node.children[c]
if next_node.word:
result.append(next_node.word)
next_node.word = None
board[i][j] = '#'
for di, dj in [(-1,0),(1,0),(0,-1),(0,1)]:
ni, nj = i+di, j+dj
if 0<=ni<m and 0<=nj<n and board[ni][nj] != '#':
dfs_with_pruning(ni, nj, next_node, board, m, n, result)
board[i][j] = c
# Prune: if the node has no more children and no word, remove it
if not next_node.children and not next_node.word:
del node.children[c]
print('Leaf pruning removes exhausted trie branches during search')ノードに word を保存する利点
trie のリーフノードに完全な単語を保存すると、DFS のパスから再構築する場合と比べて 2 つの利点があります。(1) 一致が見つかったとき、O(L) のパス再構築ではなく O(1) で単語を取得できます。(2) 単語を見つけた後に node.word = None と設定すれば、別の結果用 set を使わずに、O(1) で重複を除去できます。特に Word Search II では、同じ単語が異なるパスから見つかる可能性があるため、重複防止が重要です。
訪問済みセルをその場でマークする
別の visited set を使うと DFS のパスごとに O(m × n) の空間が必要になります。その代わりに、セルの文字を '#' のようなセンチネルに置き換えて、その場でマークします。DFS が戻ったら元の文字を復元します。この手法には、(1) セルごとの追加領域を O(1) にできる、(2) 1 つのパス内での再訪を自動的に防げる、(3) '#' が trie に存在することはないため、trie の走査に完全に透過的である、という利点があります。
考慮すべきエッジケース
重要なエッジケースは次のとおりです。(1) 単語リスト内の重複単語 — set に格納するか、node.word = None の方法を使って結果の重複を防ぎます。(2) ボードのサイズを超える非常に長い単語 — 作成できませんが、DFS は隣接セルがなくなることで自然に処理を終了します。(3) 1 セルだけのボード — 見つけられるのは 1 文字の単語だけです。(4) 異なるパスで同じ単語を見つけられる場合 — node.word = None の方法で二重カウントを防ぎます。
単純なアプローチとの比較
単純なアプローチでは、W 個の各単語に対して Word Search I を実行するため、計算量は O(W × m × n × 4^L) です。trie を使うと、W の値に関係なく、すべての単語を O(m × n × 4^L) で同時に検索できます。長さ 10 の単語が 1000 個あり、10×10 のボードを使う場合、単純な方法は trie を使う方法より 1000 倍遅くなります。trie は共有プレフィックスのフィルターとして機能し、すべての単語に処理コストを分散させます。これは、データ構造を使って漸近的な改善を実現する典型的な例です。
完全な解法のまとめ
Word Search II の完全な解法は次のとおりです。単語を使って trie を構築し、リーフに単語の文字列を保存します。各ボードセルに対して DFS を実行し、現在の文字が現在の trie ノードに存在するか確認して、セルを '#' に変更し、4 つの近傍へ再帰し、セルを復元します。node.word が null でなければ結果に追加し、null に設定します。必要に応じて、使用後に空になった trie の分岐を枝刈りします。結果のリストを返します。時間計算量は O(m×n×4^L)、空間計算量は O(W×L) の trie と O(L) の再帰です。
class TrieNode:
def __init__(self):
self.children = {}
self.word = None
def findWords_final(board, words):
root = TrieNode()
for word in words:
node = root
for c in word:
node = node.children.setdefault(c, TrieNode())
node.word = word
m, n = len(board), len(board[0])
result = []
def dfs(i, j, node):
c = board[i][j]
child = node.children.get(c)
if not child:
return
if child.word:
result.append(child.word)
child.word = None
board[i][j] = '#'
for di, dj in [(-1,0),(1,0),(0,-1),(0,1)]:
ni, nj = i+di, j+dj
if 0<=ni<m and 0<=nj<n and board[ni][nj] != '#':
dfs(ni, nj, child)
board[i][j] = c
if not child.children:
del node.children[c]
for i in range(m):
for j in range(n):
dfs(i, j, root)
return result理解度チェック
このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、Word Search II では trie を使うことで、共有プレフィックスの枝刈りを利用した複数単語の同時検索が可能になること、trie のリーフに単語の文字列を保存すると O(1) で単語を取得でき、見つけた後に None を設定するだけで簡単に重複を除去できること、そして'#' による訪問済みセルのその場でのマーキングによって、DFS のパスごとに O(m×n) の追加領域を使わずに済むことを学びました。これで Tries and String Algorithms コースは完了です。面接で使われる、文字列に特化した最も強力なデータ構造の 1 つを習得しました。
よくある質問
「Word Search II：Trie＋グリッド上のバックトラッキング」レッスンは無料ですか？
はい。「Word Search II：Trie＋グリッド上のバックトラッキング」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「Word Search II：Trie＋グリッド上のバックトラッキング」で何を学びますか？
すべての対象単語をtrieに挿入し、2D盤面上でDFSバックトラッキングを実行して、O(m × n × 4^L)で有効な単語をすべて同時に見つけます。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン4/4です。
「Word Search II：Trie＋グリッド上のバックトラッキング」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- TrieNodeクラス：挿入と検索
- Prefix SearchとStarts-With
- Trieでのワイルドカードと正規表現検索
- Word Search II：Trie＋グリッド上のバックトラッキング