Word Ladder
beginWordとendWordの2つの単語と、単語のリストwordListが与えられます。ラダーはbeginWordで始まり、endWordで終わり、隣り合う単語同士でちょうど1文字だけを変更します。beginWordの後に続く単語はすべてwordListに含まれていなければならないため、endWordはwordListに含まれている必要がありますが、beginWordは含まれていなくてもかまいません。
最短のラダーに含まれる単語数を、両端の単語も数えて返してください。そのようなラダーが存在しない場合は0を返してください。
関数
- beginWordstring
- はしごの最初の単語
- endWordstring
- はしごがたどり着かなければならない単語
- wordListstring-array
- 後続するすべてのステップで使う単語の出どころ
- 戻り値integer
- 最短のラダーに含まれる単語数。存在しない場合は0
制約
1 ≤ beginWord.length ≤ 10endWordとwordList内のすべての単語は、beginWordと同じ長さです。1 ≤ wordList.length ≤ 5000- すべての単語は小文字の英字のみで構成されています。
beginWord != endWordwordListに含まれる単語はすべて異なります。beginWordはその中の1つである場合も、そうでない場合もあります。
例
- 入力
- beginWord = "lead"endWord = "gold"wordList = ["load", "goad", "gold", "lend", "lewd", "bold"]
- 出力
- 4
- 説明
leadとgoldは3文字異なるため、ラダーには少なくとも4つの単語が必要です。また、lead、load、goad、goldは4つです。lendとlewdは行き止まりです。
- 入力
- beginWord = "cat"endWord = "dog"wordList = ["cot", "cog", "dot", "dig"]
- 出力
- 0
- 説明
cat、cot、cogはdogまであと1文字のところまで近づきますが、dogはリストに含まれていないため、そこを終点とするラダーはありません。
- 入力
- beginWord = "ab"endWord = "cd"wordList = ["ab", "cb", "cd", "ad"]
- 出力
- 3
- 説明
ab、ad、cdと、ab、cb、cdはどちらも3つの単語を使います。abもリストに含まれていますが、開始語は1回だけ数えます。
発展問題
長さではなく、最短のラダーを1つ、単語を順番に並べて返すことはできますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
すべての単語を点として表し、ちょうど1文字だけ異なる2つの単語の間に線を引くとします。その図における「はしご」とは何でしょうか。また、最短のものは何でしょうか。
最短のはしごとは、行数が最も少ない経路であり、すべての行は同じように数えます。幅優先探索では、2ステップ離れた単語に到達する前に、1ステップ離れたすべての単語に到達するため、
endWordに初めて到達したとき、使用したステップ数は最少です。単語には、初めて到達した時点で訪問済みの印を付けます。単語をリスト全体と比較して隣接する単語を見つけるのは時間がかかります。代わりに、一度に1文字ずつ隠します。
hot、hat、hitはすべてh*tになります。各単語を、その単語が持つすべてのパターンのバケットに入れます。単語の隣接語は、同じバケットに入っているほかの単語です。beginWordからレベルごとに探索し、レベル数を数えます。
解説
単語をグラフのノードとして扱い、1文字だけ異なる単語同士をエッジで結びます。すべてのエッジのコストは同じなので、幅優先探索で最短の単語の梯子が見つかります。難しいのは、エッジを素早く見つけることです。以下では、n は単語数、L は単語の長さです。
深さ優先探索ですべてのはしごを試す
正しいが、最大のテストでは終わらない
考え方
現在の単語から、1文字だけ異なる未使用の単語をすべて試して、endWordに到達したときに長さを保ちながら、さらに深く進みます。経路上の単語に使用済みの印を付け、戻るときに解除します。best個の単語からなるはしごが見つかったら、best-1個の単語からなる経路をそれ以上延ばすのをやめます。
これは単語を繰り返さないすべてのはしごを試します。最短のはしごでは単語が繰り返されることはありません。同じ単語が2回現れる箇所の間を取り除けば、はしごが短くなるからです。
aaa、baaからzaaまでの26個の単語は、どれも1文字だけ異なり、約4 × 10^26通りに並べられます。endWordに到達できない場合、この打ち切り条件は発動せず、探索はそれらをすべて試します。
アルゴリズム
beginWordがリストにある場合は使用済みとしてマークし、bestを0に設定します。search(word, length)：endWordに到達したら、lengthがbestを上回る場合はbestを更新して、戻ります。bestが設定されていて、length + 1 ≥ bestの場合も戻ります。- それ以外の場合は、未使用で1文字だけ異なる各単語について、使用済みとしてマークし、
search(next, length + 1)を呼び出してから、使用済みマークを解除します。 search(beginWord, 1)の後にbestを返します。
def ladderLength(beginWord, endWord, wordList):
def one_letter_apart(a, b):
differences = 0
for x, y in zip(a, b):
if x != y:
differences += 1
if differences > 1:
return False
return differences == 1
best = 0 # words in the shortest sequence found so far, 0 while there is none
used = [word == beginWord for word in wordList] # words on the current path
def search(word, length):
nonlocal best
if word == endWord:
if best == 0 or length < best:
best = length
return
if best != 0 and length + 1 >= best:
return # any longer path cannot beat the best one
for i, candidate in enumerate(wordList):
if not used[i] and one_letter_apart(word, candidate):
used[i] = True
search(candidate, length + 1)
used[i] = False # free the word for other paths
search(beginWord, 1)
return best幅優先探索：すべてのペアを比較
正しいが、最大のテストでは終わらない
考え方
キューは距離の順に単語を探索します。つまり、距離が d の単語は、距離が d + 1 の単語より先にすべてキューから取り出されます。そのため、単語が距離 d で初めて見つかったときには、それより近いすべての単語がすでに探索済みであり、そこへ至るより短いラダーがあれば、より早くその単語に到達していたはずです。その距離はキューに追加された時点で確定するので、その時点で訪問済みとしてマークします。そして、endWord が初めて見つかったとき、その距離が答えです。
このバージョンでは、リスト内のすべての単語と比較して、2つ目の違いが見つかった時点で比較を打ち切ることで、ある単語の隣接語を見つけます。計算量は O(n² × L) で、単語が5,000個の場合、単語の比較回数は最大2,500万回です。
アルゴリズム
endWordがwordListに含まれていない場合は、0 を返します。- 長さを 1 として
beginWordをキューに入れ、リストに含まれている場合は訪問済みとしてマークします。 - 次の単語を取り出し、未訪問のすべての単語と比較します。1 文字だけ異なる場合、その単語が
endWordであれば、長さ + 1 を返します。それ以外の場合は、その単語を訪問済みとしてマークし、長さ + 1 としてキューに入れます。 - キューが空になった場合は、0 を返します。
from collections import deque
def ladderLength(beginWord, endWord, wordList):
def one_letter_apart(a, b):
differences = 0
for x, y in zip(a, b):
if x != y:
differences += 1
if differences > 1:
return False
return differences == 1
if endWord not in wordList:
return 0
visited = [word == beginWord for word in wordList]
queue = deque([(beginWord, 1)]) # (word, words in the sequence up to it)
while queue:
word, length = queue.popleft()
# Compare against every word to find the neighbours.
for i, candidate in enumerate(wordList):
if not visited[i] and one_letter_apart(word, candidate):
if candidate == endWord:
return length + 1
visited[i] = True
queue.append((candidate, length + 1))
return 0ワイルドカードバケットを使った幅優先探索
考え方
2 つの単語がちょうど 1 文字違いであるのは、同じ位置の文字を隠すと一致する場合です。hot と hit はどちらも h*t になります。各単語について、隠す位置ごとに 1 つずつ L 個のパターンを作り、それぞれのバケットに追加します。ある単語の隣接語は、その単語と同じ L 個のバケットにある他の単語です。リスト全体を走査する代わりに、L 回のハッシュ検索で見つけられます。
最初の例では、l*ad には load が入り、le*d には lend と lewd が入るため、レベル 2 はこの 3 語です。次に *oad から goad が見つかり、go*d からレベル 4 の gold が見つかります。
バケットを走査すると、その中のすべての単語に到達できるので、走査後は空にします。26 語が入ったバケット *aa は、26 回ではなく 1 回だけ走査されます。時間計算量と空間計算量は O(n × L²) で、10 文字の単語が 5,000 語の場合、文字処理は約 500,000 回です。
アルゴリズム
endWordがwordListに含まれていない場合は、0 を返します。beginWordを含む各単語を、それぞれのL個のパターンの下に分類します。beginWordを訪問済みとしてマークし、長さ 1 でキューに追加します。- 各レベルの単語について、
endWordであれば長さを返します。そうでなければ、各パターンのバケットにある未訪問の単語をすべて次のレベルに移し、訪問済みとしてマークして、バケットを空にします。 - レベルごとに長さに 1 を加えます。キューが空になった場合は、0 を返します。
from collections import defaultdict, deque
def ladderLength(beginWord, endWord, wordList):
if endWord not in wordList:
return 0
size = len(beginWord)
# "h*t" -> every word that matches it: hot, hat, hit... are one letter apart.
buckets = defaultdict(list)
for word in set(wordList) | {beginWord}:
for i in range(size):
buckets[word[:i] + "*" + word[i + 1:]].append(word)
visited = {beginWord}
queue = deque([beginWord])
length = 1 # words in the sequence up to the current level
while queue:
for _ in range(len(queue)): # one level: every word at this distance
word = queue.popleft()
if word == endWord:
return length
for i in range(size):
pattern = word[:i] + "*" + word[i + 1:]
for neighbour in buckets[pattern]:
if neighbour not in visited:
visited.add(neighbour)
queue.append(neighbour)
buckets[pattern] = [] # all of them are visited now: never scan it again
length += 1
return 0
落とし穴と境界ケース
- 単語数ではなく、変更回数を数える。
leadからgoldまでは変更が3回、単語数は4語なので、答えは4。 endWordがwordListに含まれているかどうかの確認を省略する。2つ目の例では、cogに到達するが、dogとは1文字違うだけでも、答えは0。- 単語がキューから取り出されたときに訪問済みとして記録する。すると、
*aaのバケット内の単語は最大25回も追加され、キューがnをはるかに超えて増えてしまう。 - ラダーを再帰的にたどる。最短のラダーでも数千語に及ぶことがあり、コールスタックがオーバーフローするのに十分な長さになる。
よくある質問3
Word Ladder の時間計算量はどれくらいですか？
ワイルドカードバケットを使うと、長さがLの単語n個に対してO(n × L²)となります。各単語には、L文字のパターンがL個あります。すべての単語のペアを比較するにはO(n² × L)かかり、深さ優先探索ですべての単語のはしごを試すと指数時間になります。
1文字だけ異なる単語はどのように見つけますか？
ワイルドカードバケットを使う方法があります。もう一つは、各位置を26文字すべてに置き換え、その結果を単語のハッシュセットで検索する方法です。単語あたり26 × L回の検索を行い、各単語の文字数はLなので、全体でO(n × 26 × L²)です。どちらの方法も、リスト全体を走査するより効率的です。
双方向 BFS で Word Ladder を高速化できるでしょうか？
はい。両端から同時に探索し、常に小さい側を1レベルずつ広げ、両側が出会ったら停止します。単語あたり約b個の隣接語があり、変更回数がdの場合、片側からの探索では約b^d個の単語に触れることがありますが、中央で出会う2つの探索では約2 × b^(d/2)個に触れます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def ladderLength(beginWord, endWord, wordList):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
beginWord = "lead" endWord = "gold" wordList = ["load", "goad", "gold", "lend", "lewd", "bold"]
期待される出力
4