Word Ladder
2つの単語 beginWord と endWord、および単語のリスト wordList が与えられます。ラダーとは、beginWord から始まり、endWord で終わる単語の列で、隣り合う単語同士でちょうど1文字だけが変わります。beginWord の後に続くすべての単語は、wordList に含まれていなければなりません。
最短のラダーに含まれる単語の数を、両端の単語を含めて返してください。ラダーが存在しない場合は 0 を返してください。たとえば、cold、cord、card は3語のラダーです。beginWord は wordList に含まれていなくてもかまいませんが、endWord は含まれていなければなりません。
関数
- beginWordstring
- はしごの最初の単語
- endWordstring
- はしごが到達しなければならない単語
- wordListstring-array
- 以降のすべてのステップで使用する単語
- 戻り値integer
- 最短のラダーに含まれる単語数。存在しない場合は0
制約
1 ≤ beginWord.length ≤ 10endWordとwordList内のすべての単語は、beginWordと同じ長さです。1 ≤ wordList.length ≤ 5000- すべての単語は小文字の英字のみで構成されています。
beginWord != endWordwordListに含まれる単語はすべて異なります。beginWordはその中に含まれる場合も、含まれない場合もあります。
例
- 入力
- beginWord = "lead"endWord = "gold"wordList = ["load", "goad", "gold", "lend", "lewd", "bold"]
- 出力
- 4
- 説明
leadとgoldは3文字異なるため、ラダーの単語数は少なくとも4語です。また、lead、load、goad、goldはちょうど4語です。lendとlewdもleadとは1文字違いますが、どちらも新たな行き先にはつながらず、boldにたどり着けるのはgoldからだけです。
- 入力
- 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回だけ数えます。
提出時に隠しテスト+14件
発展問題
最短の単語変換経路を1つ、単語を順番に並べて返し、その長さだけでなく経路そのものを返すことはできますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
すべての単語を点として捉え、ちょうど1文字だけ異なる2つの単語の間に線を引いてみましょう。この図でラダーとは何でしょうか。また、最短のラダーはどれでしょうか。
最短のはしごとは、行数が最も少ない経路のことで、すべての行は同じように数えます。幅優先探索では、2ステップ離れた単語に到達する前に、1ステップ離れたすべての単語に到達するため、
endWordに初めて到達したとき、使ったステップ数は最小です。単語には、初めて到達した時点で訪問済みの印を付けます。単語をリスト全体と比較して隣接する単語を探すのは時間がかかります。代わりに、1文字ずつ隠します。
hot、hat、hitはすべてh*tになります。各単語を、その単語の各パターンのバケットに入れます。ある単語の隣接する単語は、その単語が入っているバケット内のほかの単語です。beginWordからレベルごとに探索し、レベル数を数えます。
解説
単語をグラフのノードとして扱い、1文字だけ異なる2つの単語の間に辺があると考えます。ラダーはbeginWordからendWordまでのパスで、すべての辺のコストは同じなので、最短のラダーは辺の数が最も少ないパスです。幅優先探索で、まさにそれを見つけられます。この問題を難しくしているのは、辺を素早く見つけることです。5,000個の単語のすべてのペアを比較すると、比較回数は2,500万回になるため、最良の解法では代わりにワイルドカードパターンを使って隣接する単語を検索します。以下では、nは単語の数、Lは単語の長さです。
深さ優先探索ですべてのはしごを試す
正しいが、最大のテストでは終わらない
考え方
beginWordから開始します。現在の単語から、まだ使っていない1文字だけ異なる単語をすべて試し、その単語からさらに先へ進みます。endWordに到達したら、それまでで最短の場合に、梯子の長さを記録します。現在の経路上の単語を使用済みにして、梯子が同じ単語を巡回しないようにします。そして、その単語から戻るときに使用可能な状態に戻せば、ほかの梯子で使えます。best個の単語からなる梯子が見つかったら、すでにbest-1個の単語がある経路は、これ以上延長しません。それより短い経路で完了することはないからです。
この方法が正しいのは、単語を繰り返さないすべての梯子を試すからです。また、最短の梯子で単語が繰り返されることはありません。もし同じ単語が2回現れたら、その2つの間の部分を取り除くことで、より短い梯子を作れるからです。
遅いのは、梯子の数が爆発的に増えるからです。最初の文字だけが異なる26個の単語、aaa、baaからzaaまでを考えてみましょう。どの2つの単語も1文字だけ異なるため、探索は次へ進む前に、これらをどんな順番でもたどることができます。26個の単語は、約4 × 10^26通りに並べられます。枝刈りが役立つのは、梯子が見つかった後だけです。endWordにまったく到達できない場合、枝刈りは一度も行われず、単語が34個あるリストでさえ、探索を終えるにはすでに大きすぎます。また、再帰の深さは梯子と同じになり、数千個の単語に及ぶこともあります。
アルゴリズム
beginWordがリストに含まれている場合は使用済みにし、bestを0に設定します。search(word, length)を記述します。wordがendWordなら、lengthがbestを上回る場合はbestを更新して、戻ります。bestが0ではなく、length + 1 ≥ bestの場合は戻ります。この経路では最良の結果を得られません。wordから1文字だけ異なる未使用の単語すべてについて、使用済みにし、search(next, length + 1)を呼び出してから、未使用に戻します。search(beginWord, 1)を呼び出し、bestを返します。ラダーが存在しない場合、bestは0のままです。
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幅優先探索：すべてのペアを比較する
正しいが、最大のテストでは終わらない
考え方
幅優先探索では、距離の順に単語を調べます。まず beginWord、つまり1単語のはしごです。次に、それから1文字だけ異なるすべての単語、つまり2単語のはしごです。その次は、そこから1文字だけ異なる新しい単語すべて、つまり3単語のはしごとなり、このように続きます。キューによってこの順序が保たれます。単語はキューに入った順に取り出されるため、距離が d の単語は、距離が d + 1 の単語より先にすべて取り出されます。
この順序のおかげで、BFSが最初に見つけるはしごが最短になります。単語に距離 d で初めて到達したとき、距離が d より小さい単語はすべてすでに調べられています。その単語へのより短いはしごが存在するなら、探索はその単語にもっと早く到達していたはずです。同じ理由から、単語がキューに入った時点で訪問済みとしてマークしても安全です。その距離は確定しており、後で再び到達しても、距離が長くなるだけです。したがって、各単語がキューに入るのは1回だけで、endWord が隣接語として見つかった時点で、その距離が答えになります。
このバージョンでは、単語をリスト内のすべての単語と1文字ずつ比較し、2つ目の違いが見つかった時点で止めることで、隣接語を見つけます。キューから取り出される最大 n 個の単語それぞれについて、最大 L 文字の比較を n 回行うため、全体で O(n² × L) となります。単語が5,000個あり、その大半を訪れる探索では、単語の比較は最大2,500万回になります。コンパイル言語ならすばやく処理できますが、Pythonでは最大規模のテストに数秒かかります。
アルゴリズム
endWordがwordListに含まれていない場合は、0を返します。beginWordを長さ1としてキューに入れます。リストに含まれている場合は、訪問済みとしてマークします。- キューから次の単語とその長さを取り出します。
- リスト内の訪問していないすべての単語と比較します。ちょうど1文字だけ異なる単語について、それが
endWordなら長さ + 1を返し、そうでなければ訪問済みとしてマークし、長さ + 1とともに追加します。 - キューが空になった場合、
endWordには到達できません。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 回のハッシュ検索で見つけられます。
最初の例での探索を見てみましょう。lead のパターンは *ead、l*ad、le*d、lea* です。l*ad のバケットには load があり、le*d のバケットには lend と lewd があるので、レベル2はこの3つの単語です。load からは、*oad のバケットによってレベル3の goad が見つかり、さらに goad からは、go*d によってレベル4の gold が見つかります。
もう1つ、処理を節約できます。ある単語のバケットを走査し終えたら、その中の単語にはすべて到達済みなので、バケットを空にします。同じパターンを共有する後続の単語がそのバケットを調べても、新たに見つかるものはないからです。aaa、baa から zaa までが *aa を共有するテストでは、26個の単語が入ったこのバケットは26回ではなく1回だけ走査されます。つまり、探索中に各 n × L 個のバケット要素が読み取られるのは最大1回です。
パターンの構築には、長さ L の文字列が n × L 個必要で、時間計算量と空間計算量は O(n × L²) です。探索も同じ計算量になります。キューから取り出される各単語について、L 個のパターンを再び構築するためです。長さ10の単語が5,000個の場合、文字の処理回数は約500,000回です。一方、単語をペアごとに比較すると、最大2億5,000万回に達することがあります。
アルゴリズム
endWordがwordListにない場合は、0を返します。- リスト内のすべての単語と
beginWordについて、その単語を各Lパターンのバケットに追加します。 - キューに
beginWordを入れて開始し、訪問済みとしてマークし、長さを1に設定します。 - キューを一度に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
落とし穴と境界ケース
誤答の多くは、数える対象を間違えるか、endWordに関するルールを誤解することで起こります。
- 変更回数を返し、単語数を返さない。
leadからgoldへの変換には変更が3回、単語が4つ必要なので、答えは4です。 endWordがwordListに含まれているかを確認しない。2つ目の例では、探索はdogから1文字だけの単語に到達しますが、答えは0です。- 深さ優先探索を使い、最初に見つかった変換ラダーを返す。DFSは1つの分岐を進めるだけ進むため、最初に見つかるラダーは長いことがよくあります。
- 単語がキューに入るときではなく、キューから取り出されるときに訪問済みとしてマークする。26個の単語が入ったバケットでは、その単語がキューに最大25回入ることがあり、キューのサイズは
nを大幅に超えて増えます。 beginWordもwordListに含まれている場合に、これを未訪問のままにする。すると探索は2レベル後に再びそこへ到達し、処理を繰り返します。最初から訪問済みとしてマークしてください。- 異なる文字が最大1文字の単語を調べる。どの単語も自分自身とは0文字異なるので、条件はちょうど1文字です。
- ラダーに沿って再帰する。非公開テストには、最短ラダーが1,500語になるものがあり、一部の言語では呼び出しスタックがあふれるほど深くなります。BFSで必要なのはキューだけです。
よくある質問4
幅優先探索では、なぜ最短のワードラダーが見つかるのでしょうか？
BFSは単語を段階的に探索します。まず開始単語を探索し、次に1回の変更で到達できるすべての単語、その次に2回の変更で到達できるすべての単語を探索します。単語には、それに到達できる最も早い段階で初めて到達するため、その距離は可能な限り少ない変更回数になります。これは、すべての変更のコストが同じ場合にのみ成り立ちます。各ステップのコストが異なる場合は、代わりにDijkstraのアルゴリズムが必要です。
Word Ladder の時間計算量はどれくらいですか？
ワイルドカードバケットを使う場合、パターンの作成と検索の実行には、長さLの単語がn個あるとき、O(n × L²)の時間がかかります。各単語には、L文字からなるパターンがL個あるためです。単語のすべてのペアを比較する場合はO(n² × L)のコストがかかり、深さ優先探索ですべてのラダーを試すと指数時間になります。
1文字だけ異なる単語は、どうやって見つけますか？
1つの方法は、上にあるワイルドカードバケットです。h*tのようなパターンを共有する単語は隣接しています。もう1つは、単語の各位置を26文字それぞれに置き換え、結果を単語のハッシュセットで検索する方法です。単語ごとに26 × L回の検索が必要で、各検索ではL文字をハッシュ化するため、合計でO(n × 26 × L²)となります。どちらの方法も、リスト全体と比較するより効率的です。
双方向BFSでWord Ladderを高速化できる？
はい。beginWordとendWordの両方から同時に探索し、常に小さい側を1レベルずつ広げ、新しい単語にもう一方の側がすでに到達していたら停止します。ラダーの単語数は、両側で行った変更の合計より1つ多くなります。各単語に約b個の隣接語があり、ラダーにd回の変更が必要な場合、1回の探索では約b^d個の単語に触れるのに対し、途中で合流する2回の探索では約2 × b^(d/2)個の単語に触れます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def ladderLength(beginWord, endWord, wordList):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
beginWord = "lead" endWord = "gold" wordList = ["load", "goad", "gold", "lend", "lewd", "bold"]
期待値
4