プロンプトと適用可能なコンテキスト
beginWord、endWord、および wordList が与えられたとき、最短変換シーケンスの長さを求めてください。 隣接するすべてのペアは正確に1箇所の位置のみが異なる必要があり、beginWord より後のすべての単語（endWord を含む）は辞書に存在しなければなりません。返される長さは変更回数ではなく単語数をカウントします。
beginWord = "hit"
endWord = "cog"
wordList = ["hot", "dot", "dog", "lot", "log", "cog"]
One shortest sequence:
hit -> hot -> dot -> dog -> cog
Return: 5標準的な契約を使用します：beginWord と endWord は異なり、すべての単語は小文字の英字を含み、すべての辞書の単語は同じ長さ L を持ち、辞書のエントリは一意であり、エントリ数は最大で N = 5,000 個です。endWord が存在しないか到達不可能な場合は、0 を返します。
これはグラフ構造が文字列の内部に隠されているグラフ問題です。各有効な単語が頂点であり、1文字だけ異なる2つの単語は無向のコスト1のエッジを共有します。したがって、プロンプトは非重み付きグラフにおける単一ペア最短経路を求めています。2026年時点の公開されているグラフ面接資料でも、Word LadderはBFS変換問題として記載されており、2026年6月の公開面接記録ではより難易度の高い Word Ladder II のバリアントが議論されています。これらの記録は現在の対策価値を示すものであり、面接での出題頻度や確認済みの企業帰属を証明するものではないため、本記事ではいずれの主張も行いません。
面接官が評価するポイント
第1の評価シグナルは、候補者が暗黙のグラフを認識できるかどうかです。辞書内のすべての単語ペアを比較すると正しいグラフが構築されますが、O(N²L) 回の文字比較が必要になります。より優れた回答では、現在の単語の可能な隣接ノードのみを生成します。すなわち、L 個の文字のそれぞれを他の25文字に置き換え、ハッシュセットを使用して辞書に含まれているかを判定します。
第2の評価シグナルは、最短経路の論証です。各変換のコストは1ステップであるため、BFSは距離が非減少の順序で状態を探索します。DFSは最終的にパスを見つける可能性がありますが、最初に見つかるパスが最短であるとは限りません。Dijkstraは重みが1であれば正しいものの、情報量を増やすことなく優先度付きキューのオーバーヘッドを追加するだけです。
第3の評価シグナルは、訪問済み（visited）の記録タイミングです。単語は、後で展開される時ではなく、フロンティアに入る時点で未訪問セットから削除されなければなりません。マーキングを遅らせると、複数の親ノードが同じ単語をエンキューしてしまい、計算量とメモリの両方が増加します。双方向BFSでは、生成された隣接ノードは、未訪問セットに対してチェックされる前に、反対側の現在のフロンティアに対してチェックされなければなりません。
第4の評価シグナルは、最適化の正当性を証明できるかどうかです。双方向BFSは、各端点から1レベルのフロンティアを保持し、より小さい方のフロンティアを展開します。これにより、木構造状の探索を約 b^d の状態から、b^(d/2) 付近の2つの探索へと削減できることが多くなります（ここで b は実効分岐数、d はエッジ数での解）。ただし、最悪ケースの漸近的上限は改善されません。敵対的に構成された辞書では、アルゴリズムがほぼすべての単語を検査せざるを得ない場合があります。
最後に、優れた回答では実際の文字列操作コストを明示します。展開される各単語は最大で 25L 個の変異を試みます。Pythonにおいて候補文字列を作成するコストは O(L) であるため、固定の26文字アルファベットに対する実装の期待時間計算量は O(NL²)、文字の格納空間は O(NL) となります。これを O(NL) と呼ぶことは、文字列構築を暗黙のうちに定数時間として扱うことになります。
回答前の確認質問
- 戻り値は正確に何をカウントしますか？ この契約では両方の端点をカウントします。したがって、直接の有効な変換は
2を返します。エッジ数をカウントするAPIの場合は1少なくなります。 endWordは辞書に含まれている必要がありますか？ はい。含まれていない場合は探索前に0を返します。ターゲットが辞書外にあってもよいバリアントでは、この早期リターン規則が変化します。- すべての単語は同じ長さで、同じアルファベットですか？ はい。長さは
L、小文字の英字です。Unicode、異なる長さ、またはより大きなアルファベットの場合は、隣接ノードの生成方法とそのコストが変わります。 - エントリは一意ですか？ はい。入力をセットに変換することは、期待定数時間での所属判定および訪問済み削除のために有用です。重複が許可されていたとしても、異なる頂点が作成されるわけではありません。
- 必要なのは1つの長さですか、1つの経路ですか、それともすべての最短経路ですか？ 基本問題で必要なのは長さのみです。経路を返すには親マップが必要になり、すべての最短経路を返すには同じBFSレベルからのすべての親を保持する必要があり、同じ即時削除ルールを変更なしで使用することはできません。
- これは単一のクエリですか、それとも静的な辞書に対する多数のクエリですか？ 単一クエリの場合、オンデマンドの変異生成がシンプルであり、完全なインデックス作成を回避できます。繰り返しクエリを実行する場合は、再利用可能なワイルドカードパターンインデックスの作成が正当化される可能性があります。
beginWordは最初から辞書に含まれていてもよいですか？ はい。それでも1つの頂点であり、初期化中に未訪問セットから削除する必要があります。
30秒の回答フレームワーク
「各単語を頂点としてモデル化し、1文字だけ異なる2つの単語を接続します。すべてのエッジのコストは1回の変換であるため、これは非重み付き最短経路問題です。beginWord と endWord から双方向BFSを実行し、常にサイズの小さい方の完全なレベルフロンティアを展開します。フロンティアの各単語について、最大 25L 通りの1文字変異を生成し、ハッシュセットでテストします。変異が反対側のフロンティアに存在する場合、2つの探索済み最短プレフィックスが最短シーケンスを形成するため、現在の単語カウントに1を加えた値を返します。そうでない場合は、有効な未訪問単語を次のフロンティアに追加した直後に削除します。endWord が存在しないか、フロンティアが空になった場合は0を返します。最悪ケースでは依然として N 個の単語を訪問します。Pythonの候補構築で L 文字がコピーされるため、時間は O(NL²)、格納される文字列コンテンツは O(NL) となります。直接変換、到達不能、閉路、重複発見、および非対称フロンティアのケースをテストします。」
ステップバイステップの詳細解説
グラフモデルから始めます。頂点セットにはすべての辞書の単語と beginWord が含まれるとします。同じ長さの任意の2つの単語について、それらのハミング距離が1である場合にのみエッジを追加します。グラフは無向です。hot が dot に変更できるなら、逆の変更も有効です。正当な変更はすべて1つのエッジを構成するため、非重み付きです。
明示的なペアワイズグラフは O(N²) ペアを比較し、比較ごとに O(L) を費やします。これは、ほとんどのペアが無関係である場合でも O(N²L) の前処理となります。入力アルファベットにより、候補空間はより小さくなります。単語は最大で 25L 個の異なる1文字変異を持ち、辞書に含まれるかどうかがそれらが実際の頂点であるかを決定します。
片方向BFSはすでに正当です。その不変条件は以下のとおりです：
At the start of level k:
the frontier contains exactly the discovered words at edge distance k;
no undiscovered word has distance less than k;
every word outside unvisited has already been assigned its minimum distance.BFSはレベル k + 1 をレベル k からのみ作成します。したがって、単語が最初に発見されたときの経路が最短経路となります。発見時に単語を unvisited から削除することで、その事実が維持され、重複したフロンティアエントリが防止されます。
既知の単一ターゲットの場合、両方の端点から探索します。front は開始側からの完全な1レベルであり、back は終了側からの完全な1レベルです。sequence_length は、まだ接続エッジがない状態で両端のフロンティア単語をカウントするため、現在のエッジ深さの合計に1を加えたものと等しくなります。いずれかのフロンティア全体を展開すると、その深さの合計は1増加します。生成された単語が反対側のフロンティアに属している場合、接続エッジによって答えは sequence_length + 1 となります。
小さい方のフロンティアを展開することはパフォーマンスを変更するだけであり、正当性には影響しません。2つのセットを入れ替えても、次に進める有効なBFSレイヤーが変わるだけであり、各セットは依然としてそれぞれの起点からの正確な深さを表します。反対側の現在のフロンティアとの交差をチェックすることが不可欠です。一方の側が単語を発見した際に即座にそれを確保するため、単一のグローバルな unvisited セットで安全です。後の展開がもう一方の探索のすでに展開されたレイヤーへのエッジを持っていた場合、その以前の展開によって同じ単語が先に発見されていたはずであるため、探索が現在のフロンティアの背後で気付かずに交差することはありません。
ALPHABET = "abcdefghijklmnopqrstuvwxyz"
def ladder_length(
begin_word: str,
end_word: str,
word_list: list[str],
) -> int:
unvisited = set(word_list)
if end_word not in unvisited:
return 0
front = {begin_word}
back = {end_word}
unvisited.discard(begin_word)
unvisited.remove(end_word)
sequence_length = 1
while front and back:
if len(front) > len(back):
front, back = back, front
next_front: set[str] = set()
for word in front:
for index, original in enumerate(word):
for letter in ALPHABET:
if letter == original:
continue
candidate = word[:index] + letter + word[index + 1 :]
if candidate in back:
return sequence_length + 1
if candidate in unvisited:
unvisited.remove(candidate)
next_front.add(candidate)
front = next_front
sequence_length += 1
return 0フロンティアレイヤーによるサンプルのトレース：
| 展開 | 開始側のフロンティア | 終了側のフロンティア | 展開前のカウント |
|---|---|---|---|
| 1 | hit | cog | 1 |
| 2 | hot | cog | 2 |
| 3 | dot, lot | cog | 3 |
| 4 | dot, lot | dog, log | 4 |
アルゴリズムは展開3で、より小さい cog 側を展開します。展開4で、dot が dog に到達するか、lot が log に到達するため、5 を返します。セットのイテレーション順序によって異なる最短合流エッジが選択される可能性がありますが、長さは変わりません。
N を辞書のサイズ、L を単語の長さとします。各単語は最大で1回フロンティアに追加され、展開される場合は 25L 個の候補を試します。ハッシュルックアップの期待値は O(1) ですが、Pythonのスライスと連結による各候補生成のコストは O(L) であり、固定アルファベットにおける最悪ケースの期待時間計算量は O(NL²) となります。セットは最大で O(N) 個の参照を保持し、その文字列には O(NL) 文字が含まれます。一時的な候補文字列は一度に O(L) を追加します。面接で変更可能な固定長文字バッファを使用し、候補の実体化やハッシュ計算を O(L) として扱う場合でも、同じ厳密な上限が適用されます。
ワイルドカードインデックスが主な代替手段です。h*t、*ot、ho* などのパターンを一致する単語に対応付けます。これは多数のクエリ間で再利用でき、辞書に存在しない文字を試す無駄を回避できます。Pythonにおいて、N 個の単語に対して L 個のパターン文字列を作成するコストも O(NL²) の文字操作となり、O(NL) 個のバケットエントリを保持する可能性があります。BFSの実行中は、消費されたパターンバケットをクリアするか処理済みとして追跡する必要があります。そうしないと、多数の単語に対して同じ大きなバケットをスキャンしてしまい、二次オーダーの計算量が再発する可能性があります。規定された制約下での単一クエリに対しては、変異生成とセットを組み合わせる方が可動部品が少なくなります。
サンプルだけでなく、実行可能な契約をテストしてください：
cases = [
(
"hit",
"cog",
["hot", "dot", "dog", "lot", "log", "cog"],
5,
),
("hit", "cog", ["hot", "dot", "dog", "lot", "log"], 0),
("a", "c", ["a", "b", "c"], 2),
("red", "tax", ["ted", "tex", "red", "tax", "tad", "den", "rex", "pee"], 4),
("aaa", "bbb", ["aab", "abb", "bbb", "aba", "baa"], 4),
]
for begin_word, end_word, words, expected in cases:
actual = ladder_length(begin_word, end_word, words)
assert actual == expected, (begin_word, end_word, actual, expected)プロパティベーステストでは、小さなランダム辞書を生成し、明示的なペアワイズグラフを信頼できるオラクルとして構築し、その通常のBFS結果を最適化された関数と比較できます。また、入力リストを変更しないままにし、一方のフロンティアがもう一方よりもはるかに速く成長する辞書をテストし、複数の親を通じて到達可能な単語が1回だけ展開されることを確認してください。
質の高い模範解答
「単語は暗黙の無向グラフを形成します。頂点は有効な単語であり、エッジはハミング距離が1の単語を接続します。すべてのエッジのコストは1であるため、BFSによって最小変換数が得られます。単語数を返すため、hit -> hot の長さは2になります。
まず辞書をセットに格納し、endWord が存在しないケースを拒否します。各端点に1つのフロンティアを保持し、どちらの探索でも発見されていない単語のセットを1つ保持します。各反復で、より小さい完全なフロンティアを展開します。各単語と文字位置について、他の25個の小文字を試します。まず反対側のフロンティアに対して候補をチェックします。一致すれば2つのBFSプレフィックスが接続されるため、答えは累積された単語カウントに1を加えたものになります。そうでない場合で候補が未訪問であれば、即座に削除して次のフロンティアに追加します。
不変条件は、各フロンティアがその端点から正確に1つの距離レイヤーにあり、削除されたすべての単語はそれを発見した側からの最小距離をすでに持っているということです。小さい側を展開してもそれらのレイヤーは変わりません。より短い経路が存在すれば、より早い2つのレイヤーが接続されていたはずであるため、最初のフロンティア接続が最短となります。即時削除により重複した発見が防止されます。
最大で N 個の単語が展開されます。それぞれが 25L 通りの変異を試し、Pythonは各候補の構築に O(L) を費やすため、期待時間計算量は O(NL²)、格納文字数は O(NL) となります。双方向探索は通常、探索状態を削減しますが、最悪ケースは同一です。繰り返しクエリに対しては再利用可能なワイルドカードインデックスを検討しますが、この1回限りのクエリに対しては変異生成の方がシンプルです。公式サンプル、ターゲットの欠落、直接変換、複数の最短ルート、閉路、およびランダムな明示的グラフオラクルを用いて検証します。」
よくある間違い
- DFSを実行して最初に見つかったパスを返す → DFSは変換数順にパスを訪問しない → すべてのエッジが単位コストであるためBFSを使用する。
- すべての辞書ペアを比較する → グラフ構築に
O(N²L)かかる → 展開される単語ごとに最大25L個の候補隣接ノードを生成する。 - ポップされた時にのみ単語を訪問済みとしてマークする → 複数の親ノードがそれをエンキューできる → フロンティアに追加する際に
unvisitedから削除する。 - 反対側のフロンティアの前に
unvisitedのみをチェックする → 合流する単語はもう一方の探索によってすでに削除されている → 最初に反対側の現在のフロンティアをテストする。 - 常に
frontという名前の側を展開する → 一方の側が爆発的に増加し、もう一方は小さいままになる可能性がある → 入れ替えて、より小さい完全なレベルフロンティアを展開する。 - エッジカウントと単語カウントを混同する → サンプルが5ではなく4を返す → シーケンスカウントを1に初期化し、合流エッジで接続単語を追加する。
- 双方向BFSが最悪ケースの計算量を改善すると主張する → 密な敵対的辞書では、依然としてほぼすべての単語が露出する可能性がある → 分岐係数の利点を保証されたものではなく一般的であると説明する。
- Pythonの変異生成を
O(NL)と呼ぶ → すべての候補がL文字をコピーまたはハッシュする → 文字列操作モデルを明示し、この実装にはO(NL²)を使用する。 - 消費せずにワイルドカードバケットを再利用する → 同じ大きなリストが繰り返しスキャンされる → 処理された各パターンバケットをクリアするか、消費済みとしてマークする。
- 1つのグローバルな訪問済みセットを使用しながら部分的なレベル展開を許可する → 合流順序と距離の計算を証明することが困難になる → 一度に完全な1フロンティアレベルを進める。
- 自己申告の企業経験談を確認済みの帰属として引用する → 公開投稿は雇用主の公式記録ではない →
companyNameを null のままにし、記録を現在の公開証拠としてのみ使用する。
フォローアップとその対処法
フォローアップ1：実際の最短シーケンスの1つを返すにはどうすればよいですか？
方向ごとに親マップを保持します。候補が発見されたら、それを生成した単語を記録します。合流エッジにおいて、開始側の親マップを beginWord まで遡り、そのプレフィックスを反転させ、終了側の親マップを endWord に向かって辿ります。実装でフロンティア変数を入れ替える可能性があるため、現在の front が常に開始側であると仮定するのではなく、意味的な方向によって親マップを格納します。親マップのストレージは、辞書文字列に加えて O(N) 個の参照となります。
フォローアップ2：すべての最短シーケンスを返すWord Ladder IIでは何が変わりますか？
単語ごとに1つの親では不十分です。通常のレベル順BFSの方が論理的に把握しやすい場合が多くなります。最小レベルで単語に到達するすべての先行ノードを収集し、レベル全体が終了した後にのみ、新しく発見された単語をグローバル辞書から削除します。これにより、より長いパスが後から親を追加することを防ぎつつ、同じレベルの複数の親を許可できます。endWord に到達する最初のレベルを完了した後に停止し、先行ノードのDAGをバックトラックします。出力サイズは指数関数的になる可能性があるため、計算量には返されるシーケンスの総数と長さを含める必要があります。
フォローアップ3：通常の片方向BFSが好まれるのはどのような場合ですか？
辞書が小さい場合、一方の端点しか分かっていない場合、グラフが有向であり逆方向の隣接ノード取得が高コストである場合、またはフロンティアの削減よりもコードのシンプルさが重要な場合に使用します。片方向BFSは不変条件が少なく、親の再構築が簡単になります。このPython表現において、同じ隣接ノードジェネレータと同じ O(NL²) の上限を維持します。
フォローアップ4：ワイルドカードパターンバケットを構築するのはどのような場合ですか？
多くのクエリが静的な辞書を共有している場合、アルファベットが大きい場合、またはすべてのアルファベット置換を生成することが無駄になる場合に構築します。インデックスを辞書とともにバージョニングし、インデックス化されていない場合はクエリごとに beginWord 個のパターンを含め、探索ごとに各バケットを最大1回消費します。トレードオフは、前処理時間、バケットのメモリ、および単語が変更された際の無効化処理です。
フォローアップ5：文字変更ごとにコストが異なる場合はどうなりますか？
グラフは重み付きになり、BFSレイヤーは最小コストを表さなくなります。非負のコストに対してはDijkstraを使用し、同じ暗黙の隣接ノードを生成しながら、累積コストによってフロンティアを順序付けます。有効で許容可能なヒューリスティックがあればA*をサポートできますが、ハミング距離は残りの文字変更コストの証明された下限によってスケーリングされた後にのみ許容可能となります。
フォローアップ6：アルファベットがUnicodeの場合や単語の長さが異なる場合はどうなりますか？
まず正当な操作を定義します。Unicodeコードポイントと書記素クラスタは異なる単位であり、挿入や削除の操作は長さを変化させるエッジを導入します。直接の置換生成ではグラフを網羅できなくなります。契約に応じて、インデックス化された編集距離1の隣接探索、トライ木、または長さとパターンのバケットを使用し、等価性とハッシュ計算に正規化ルールを含めます。
フォローアップ7：面接で双方向の停止条件をどのように証明しますか？
現在の各フロンティアに、それぞれの端点からの深さを割り当てます。アルゴリズムは反復ごとに正確に1つの完全な深さレイヤーを進めます。展開の前では、sequence_length は2つのフロンティアの深さに1を加えたものになります。したがって、反対側のフロンティアへの生成されたエッジは、sequence_length + 1 個の単語を持つパスを形成します。より短いパスが存在する場合、より小さい深さの合計を持つ2つのレイヤー間にエッジが含まれることになり、それらのレイヤーはすでに展開されて接続されていたはずです。これは、これが最初のフロンティア合流であることと矛盾します。
フォローアップ8：最適化された探索を例題以外でどのように検証しますか？
小さなランダム辞書に対して、ハミング距離が1であるすべてのペアを明示的に接続し、プレーンなBFSオラクルを実行します。生成された数千のケースにわたって、その答えを双方向BFSと比較します。いずれのフロンティアも unvisited と交差しないこと、どの単語も2回発見されないこと、および次のフロンティアのすべての単語が現在のフロンティアの単語と1文字だけ異なるという不変条件を追加します。これにより、いくつかの選ばれた出力から正当性の証拠を分離します。