Word Search
文字のグリッド board と文字列 word が与えられます。board は文字列のリストであり、board[r][c] は行 r、列 c の文字を表します。
グリッド上で word をたどれる場合は true を返してください。任意のセルから開始し、各ステップで現在のセルの真上、真下、左隣、または右隣のセルへ移動して、訪れたセルの文字が順番に word をつづるようにします。同じセルを2回使用することはできません。それ以外の場合は false を返してください。文字は大文字と小文字が区別されるため、a と A は異なります。
関数
- 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
- 説明
- 0行0列の
Sから始め、右へ進んでT、下へ進んでO、右へ進んで2つ目のO、右へ進んでL、そして下へ進んで2行3列のSに到達します。これは6つの異なるセルで、それぞれが1つ前のセルに隣接しています。
- 入力
- board = ["STAR", "POOL", "ENDS"]word = "POP"
- 出力
- false
- 説明
- 盤面には、1 行目、0 列目に
Pが 1 つあります。PとOの後にはもう 1 つPが必要ですが、唯一のPは経路が始まったセルにあり、そのセルは 2 回使えません。
- 入力
- board = ["STAR", "POOL", "ENDS"]word = "SAND"
- 出力
- false
- 説明
SANDのすべての文字は盤面にありますが、最初の一歩で経路が途切れます。唯一のAは行0、列2にあり、どちらのSもそこに隣接していません。
提出時に隠しテスト+23件
発展問題
はいかいいえではなく、ボード上にwordの異なるなぞり方がいくつあるか数えられますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
単語の開始位置として、すべてのセルを試してみましょう。あるセルが現在の文字と一致したら、次の文字はどのセルにある可能性がありますか？
これは経路を探索します。各文字で最大4つの隣接セルから1つを選び、選択を間違えたら一歩戻って別のものを試します。経路上でセルを再利用できないため、現在の経路上にある間はセルに印を付け、そこから戻るときに印を外します。
dfs(r, c, i)を記述します。(r, c)がグリッドの範囲外にある場合、すでに経路上にある場合、またはword[i]と一致しない場合は失敗とします。iが最後のインデックスなら成功です。それ以外の場合は、そのセルに印を付け、i+1で4つの隣接セルを試し、印を消して、いずれかの隣接セルで成功したかどうかを返します。探索する前に、ボードに各文字が十分な数だけあることを確認し、出現頻度の低い文字がある方の単語の端から探索を開始します。
解説
これに答える公式はありません。グリッド内の経路を探す必要があります。バックトラッキングでは、一度に1つの経路を調べます。経路を1文字ずつ伸ばし、経路がそのセルを使っている間はマークし、戻るときにマークを解除します。これにより、1つの経路内でセルが再利用されることはありませんが、ほかのすべての経路では自由に使えます。最悪の場合、この探索は単語の長さに対して指数時間になりますが、6 × 6 以下の盤面なら問題ありません。その前に行う2つの簡単なチェック、文字数の確認と、単語の出現頻度が低い方の端から探索を始めることによって、数万ステップかかる処理を数十ステップにまで減らせることがよくあります。
訪問済みグリッドによるバックトラッキング
考え方
決定木を思い浮かべてください。最初の選択肢は開始セルで、そこには word[0] がなければなりません。その後、各ノードは最初の i 文字を綴る経路であり、その子ノードは word[i] を持ち、まだ経路上にない隣接セルです。単語全体を綴る経路が見つかれば成功です。そのような隣接セルがない経路は行き止まりなので、戻って次の選択肢を試します。
visited グリッドによって、各セルを一度だけ使うルールを守ります。経路がセルに進んだら印を付け、経路がそのセルから戻ったら印を外します。この印を外す処理がバックトラッキングの要です。行き止まりまで進んだ経路が通ったセルは、次の試行のために再び使える状態にしなければなりません。単語が AAA で、盤面が AA / AB の場合を考えてみましょう。左上のセルから始めると、下に進んでも左下で行き止まりになります（もう一方の隣接セルは B です）。右に進んでも右上で行き止まりになります。もしそれらのセルの印を付けたままにすると、左下、左上、右上の順に進む答えは決して見つかりません。
これは標準的な解法で、ここでは正しく、十分に高速です。計算量は探索する経路の数に応じて増えます。最初の移動の後、各ステップで新たに進める方向は最大3つなので、L 文字の単語では、およそ m·n·3^L 本の経路を探索する可能性があります。すべて A の 5 × 5 の盤面と、8 個の A の後に B が続く単語を考えてみましょう。A だけからなる経路はすべて有効な接頭辞なので、探索は B が存在しないとわかるまで、そのような経路をすべてたどります。false と答えるために、セルを約 65,000 回チェックします。文字が1つ増えるごとに、この回数はおよそ2倍になるため、次の方法では探索前にいくつかの点を確認します。
アルゴリズム
- 盤面のサイズに合わせた、すべての値が false の
visitedグリッドを作成します。 dfs(r, c, i)を定義します。(r, c)がグリッドの範囲外、訪問済み、またはその文字がword[i]と異なる場合は false を返します。iがwordの最後のインデックスであれば、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が8個ありBがないボードでは、約65,000回のチェックをする代わりに、探索なしで答えが分かります。出現頻度の低い方の端から始めます。経路を逆向きにたどっても同じセル上で逆順の単語を綴れるため、代わりに逆順の単語を探索できます。ボード上で最後の文字の方が最初の文字より出現頻度が低ければ、単語を逆順にします。探索を開始できるセルが少なくなり、出現頻度の低い文字によって、最後ではなく最初の手順で誤った開始位置を除外できます。
2つ目のルールは、出現頻度の低い文字が存在していても、そこから先へ進めない場合に重要です。唯一のBを、隣接する2つのセルがCである角に置き、8個のAの後にBが続く単語を探索します。文字数の条件は通過します。前から探索すると、探索は依然としてすべてのAの経路をたどり、セルのチェックは約35,000回になります。逆順なら、単語はBから始まり、開始できるセルは1つだけです。その隣接セルはAではないため、探索は約30回のチェックで終了します。
最悪の場合の計算量は依然としてO(m·n·3^L)です。文字の数が均等で、行き止まりに至るのが遅いボードと単語を作れるからです。この枝刈りによって答えも計算量の上限も変わりません。文字数を数えるための1回の走査が必要になりますが、単純な探索で時間を浪費するよくあるパターンを取り除き、単語が長くなるほどその差は急速に大きくなります。
アルゴリズム
- ボード上と単語内の各文字を数えます。単語に必要な文字数がボード上の数を超えていたら、false を返します。
- ボード上にある
word[0]の数が最後の文字の数より多い場合は、wordを逆順にします。 - 変更できる文字のグリッドにボードをコピーします。
dfs(r, c, i)を定義します。セルがword[i]でなければ失敗します。iが最後のインデックスなら成功します。それ以外の場合、セルを#に設定し、範囲内にある各隣接セルをi+1で試し、文字を元に戻し、成功したものがあったかどうかを返します。- すべてのセルから
dfs(r, c, 0)を実行し、成功したものがあればすぐに 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/ABでは単語AAAが false になります。 - まったくマークを付けないこと。マークを付けないと、経路が元のセルに戻ってしまう可能性があり、例の盤面で
POPは true を返します。 - 境界を確認する前にセルを読み取ること。Python では
board[-1]はエラーではなく最後の行を指すため、境界チェックを忘れるとグリッド内を静かに折り返してしまいます。 - 移動した後にだけ成功を確認すること。1文字の単語と1セルの盤面の組み合わせ、つまり
["A"]とAの場合は、セルに隣接するセルがなくても true を返さなければなりません。 - 実際の文字として使われる可能性のある文字でマークすること。たとえばセルの大文字・小文字を入れ替える方法は、
aとAの両方を使う盤面ではうまくいきません。 - 斜めに移動すること。辺を共有する4つのセルだけが隣接セルとして数えられます。
よくある質問4
Word Search の時間計算量は何ですか？
最悪の場合、m × n の盤面と長さ L の単語に対して、計算量は O(m·n·3^L) です。m·n 個の各セルから経路を開始でき、最初のステップ以降は、各セルで未訪問の隣接セルを最大 3 つ試すことができます。再帰処理に必要な追加領域は O(L) で、盤面に印を付けるためにコピーする場合は、さらに O(m·n) 必要です。
ワードサーチでマス目の印を消すのはなぜですか？
マークは、そのセルが現在の経路上にあることを意味します。分岐が失敗すると、そのセルは経路から外れ、別の経路で必要になる場合があります。マークを残しておくと、後の探索でそのセルが使用済みとして扱われ、有効なトレースを見つけられないことがあります。進入時にマークし、退出時にマークを解除します。
枝刈りによって、Word Search はどのように高速化されますか？
探索の前に2つのチェックを行います。単語に必要な文字の数が盤面にある数を超えている場合は、探索せずにfalseを返せます。また、経路を逆から読んでも単語を逆順にしたものになるため、出現頻度の低い文字がある方の端から開始できます。これにより、開始セルの数が減り、誤った経路をより早く見つけて失敗できます。どちらも最悪計算量は変わらず、単純な探索だけでも十分な答えになります。Aで埋められた5 × 5の盤面で、存在しないBが必要な単語を探す場合、これらの工夫によって約65,000回のセルチェックをゼロにできます。
Word SearchとWord Search IIの違いは何ですか？
Word Search は1つの単語について尋ねます。Word Search II では単語のリストが与えられ、そのうちどの単語が盤面に現れるかを尋ねます。単語ごとにこの検索を実行すると多くの作業が繰り返されるため、一般的な解法ではすべての単語をトライ木に格納し、盤面を一度だけ探索します。そして、文字列がその文字で始まる単語がなくなった時点で、その経路の探索を打ち切ります。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def exist(board, word):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
board = ["STAR", "POOL", "ENDS"] word = "STOOLS"
期待値
true