Word Search
文字のグリッド board と、文字列のリストが与えられます。board[r][c] は行 r、列 c の文字を表し、さらに文字列 word が与えられます。
word をたどれる場合は true を返します。任意のセルから開始し、毎回、上、下、左、または右のセルへ移動して、訪れたセルの文字が順番に word を綴るようにします。同じセルを2回使うことはできません。それ以外の場合は false を返します。大文字と小文字は区別されます。
関数
- boardstring-array
- グリッド。各行に文字列が1つ
- wordstring
- traceするという語
- 戻り値boolean
- 単語を、隣接するセルをたどって見つけられるかどうか（各セルは1回までしか使用できない）
制約
1 ≤ board.length ≤ 61 ≤ board[i].length ≤ 6であり、すべての行の長さは同じです。1 ≤ word.length ≤ 20boardとwordには、大文字と小文字の英字のみが含まれています。
例
- 入力
- board = ["STAR", "POOL", "ENDS"]word = "STOOLS"
- 出力
- true
- 説明
- 左上の
Sから始め、右に進んでTへ、下に進んでOへ、右に進んでOとLへ進み、Lの下にあるSまで下に進みます。同じマスは繰り返しません。
- 入力
- board = ["STAR", "POOL", "ENDS"]word = "POP"
- 出力
- false
- 説明
- ボードには
Pが1つあります。PとOの後にはもう1つPが必要ですが、唯一のPは開始セルなので、2回使うことはできません。
- 入力
- board = ["STAR", "POOL", "ENDS"]word = "SAND"
- 出力
- false
- 説明
SANDの各文字は盤上にありますが、唯一のA（行0、列2）はどちらのSにも接していません。
発展問題
はい／いいえではなく、ボード上でwordを作る異なる経路がいくつあるか数えられますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
単語の開始位置として、すべてのセルを試してみましょう。あるセルが現在の文字と一致したら、次の文字はどのセルにある可能性がありますか？
これは経路をたどる探索です。各文字で、最大4つの隣接セルから1つを選び、選択を間違えたら一歩戻って別のセルを試します。経路上で同じセルを再利用できないため、セルが現在の経路上にある間は印を付け、そこから戻るときに印を外します。
dfs(r, c, i)を記述します。(r, c)がグリッドの範囲外、すでに経路上にある、またはword[i]でない場合は失敗とします。iが最後のインデックスなら成功です。それ以外の場合はセルに印を付け、i+1を指定して4つの隣接セルを試し、印を消して、いずれかの隣接セルで成功したかどうかを返します。探索を始める前に、ボードに各文字が十分な数あることを確認し、出現頻度の低い文字がある方の単語の端から探索を始めます。
解説
グリッド内の経路を探索する必要があります。バックトラッキングでは、経路を1文字ずつ伸ばし、経路に含まれている間は各セルに印を付け、戻るときにその印を外すことで、同じ経路でセルが再利用されないようにします。探索量は単語の長さに対して指数関数的に増加しますが、6 × 6 の盤面なら実行できます。
訪問済みグリッドを使ったバックトラッキング
考え方
i 文字目までが一致する経路は、word[i] を持ち、その経路上にない隣接セルへ続きます。そのような隣接セルがなければ行き止まりなので、戻ります。
この処理が正しく機能するのは、マークを解除するからです。行き止まりまで進んだセルは、次の試行で使える状態にしておく必要があります。AA / AB に対して AAA を探す場合、左上からの試行はどちらも行き詰まります。セルのマークを解除しなければ、左下、左上、右上の順の答えを見つけられません。
最初の移動の後、各ステップで新たに進める方向は最大3つなので、探索では最大 m·n·3^L 個の経路を調べることがあります。A が並ぶ 5 × 5 の盤面で、A が8個続いた後に B が続く場合、false と答えるまでに約53,000回のセルチェックを行います。
アルゴリズム
visitedグリッドを作り、すべて false にする。dfs(r, c, i):(r, c)がグリッドの範囲外、訪問済み、またはword[i]と一致しない場合は false。iが最後のインデックスなら true。- それ以外の場合は
(r, c)を訪問済みにし、i+1を使って4方向の隣接セルを試し、訪問済み状態を解除して、いずれかが成功したかどうかを返す。 - いずれかのセルからの
dfs(r, c, 0)が成功した場合は true を返す。
def exist(board, word):
rows, cols = len(board), len(board[0])
visited = [[False] * cols for _ in range(rows)]
def dfs(r, c, i):
# Can word[i:] be traced starting at cell (r, c)?
if r < 0 or r >= rows or c < 0 or c >= cols:
return False
if visited[r][c] or board[r][c] != word[i]:
return False
if i == len(word) - 1:
return True
visited[r][c] = True # mark: the current path owns this cell
found = (dfs(r + 1, c, i + 1) or dfs(r - 1, c, i + 1)
or dfs(r, c + 1, i + 1) or dfs(r, c - 1, i + 1))
visited[r][c] = False # restore: other paths may use it
return found
for r in range(rows):
for c in range(cols):
if dfs(r, c, 0):
return True
return Falseインプレースのマーク付けと枝刈りを用いたバックトラッキング
考え方
2つの変更を加えて探索を続けます。盤面のコピー上でセルに#を書き込んで印を付け、戻るときに文字を元に戻します。#は単語のどの文字とも一致しないため、文字のチェックによって経路上のセルも除外されます。
次に枝刈りをします。単語に必要なある文字の数が盤面にある数より多い場合は、falseを返します。これにより、すべてがAの盤面に対して探索せずに答えを出せます。同じセルを逆順にたどると、逆順の単語ができるため、逆順の単語を探索しても答えは変わりません。盤面上で出現頻度の低い文字が末尾にある場合は、そこから探索を始めます。開始できるセルが少なくなり、条件に合わない開始位置はすぐに失敗するからです。
Bが1つだけあり、角で2つのCの間にある場合、順方向の探索では約35,000回のセルチェックが必要ですが、逆方向なら27回です。最悪の場合の計算量はO(m·n·3^L)のままです。
アルゴリズム
- 単語に必要な文字の数が、盤面にある数を超える場合は、false を返します。
- 盤面にある
word[0]の数が、最後の文字の数より多い場合は、wordを逆順にします。 - 変更できるグリッドに盤面をコピーします。
dfs(r, c, i): セルがword[i]でなければ失敗し、最後のインデックスなら成功します。それ以外の場合は、そのセルを#に設定し、範囲内の各隣接セルについてi+1で試し、セルを元に戻して、いずれかが成功したかどうかを返します。- いずれかのセルからの
dfsが成功した場合は true を返します。
from collections import Counter
def exist(board, word):
rows, cols = len(board), len(board[0])
# Pruning 1: the board must hold every letter as many times as the word uses it.
have = Counter("".join(board))
for letter, need in Counter(word).items():
if have[letter] < need:
return False
# Pruning 2: a path read backwards is the same path, so start from the
# end whose letter is rarer on the board: fewer cells begin a search.
if have[word[0]] > have[word[-1]]:
word = word[::-1]
grid = [list(row) for row in board]
def dfs(r, c, i):
# Can word[i:] be traced starting at cell (r, c)?
if grid[r][c] != word[i]:
return False
if i == len(word) - 1:
return True
grid[r][c] = "#" # mark: "#" matches no letter, so this path cannot reuse the cell
found = False
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < rows and 0 <= nc < cols and dfs(nr, nc, i + 1):
found = True
break
grid[r][c] = word[i] # restore the letter for other paths
return found
for r in range(rows):
for c in range(cols):
if dfs(r, c, 0):
return True
return False
落とし穴と境界ケース
- 失敗した分岐の後にセルの印を解除しない場合：
AAに対するAAAは false になる。 - まったく印を付けない場合：経路が最後のセルに戻り、例の盤面で
POPは true を返す。 - 境界を確認する前にセルを読み取る場合：Python では
board[-1]は最後の行なので、経路がグリッド上で折り返す。 - 移動した後にのみ成功を確認する場合：
["A"]に対するAは true を返さなければならない。 - セルの大文字・小文字を入れ替えて印を付ける場合：
["aA"]では、印を付けたaが2つ目のAとして読み取られるため、aAAは true になる。
よくある質問3
Word Search の時間計算量はどれくらいですか？
m × n のボードと長さ L の単語に対して O(m·n·3^L)：すべてのセルから経路を開始でき、最初のステップの後は、各セルに未訪問の隣接セルが最大3つあります。追加の空間計算量は、再帰に O(L)、ボードのコピーに O(m·n) です。
プルーニングによって、Word Search はどのように高速化されますか？
まず文字の数を数え、盤面にいずれかの文字が少なすぎる場合は false を返します。次に、そこから始められるセルが少ない、より希少な文字を使って、末尾から検索します。どちらのチェックも最悪計算量は変わりません。
Word Search と Word Search II の違いは何ですか？
Word Search II では、リスト内のどの単語がボード上に現れるかを調べます。単語ごとに検索すると作業が重複するため、一般的な解法では単語をトライに格納し、ボードを一度だけたどります。その文字列で始まる単語がない場合は、その経路の探索を打ち切ります。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def exist(board, word):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
board = ["STAR", "POOL", "ENDS"] word = "STOOLS"
期待される出力
true