C++で解く単語ラダー（Word Ladder）問題 ― 最短変換シーケンスの求め方

問題概要

2つの単語（beginWord と endWord）と辞書となる単語リストが与えられたとき、beginWord から endWord へ至る最短の変換シーケンスの長さを求めます。ただし、以下のルールに従うものとします。

• 一度に変換できるのは1文字だけです。
• 変換後の各単語は、必ず単語リスト内に存在しなければなりません。beginWord 自体は変換された単語としては扱いません。

さらに、以下の点にも注意が必要です。

• そのような変換シーケンスが存在しない場合は 0 を返します。
• すべての単語は同じ長さです。
• すべての単語は小文字の英字のみで構成されます。
• 単語リストに重複はないものと仮定できます。

たとえば、入力が beginWord = "hit"、endWord = "cog"、wordList = ["hot", "dot", "dog", "lot", "log", "cog"] の場合、出力は 5 になります。これは hit → hot → dot → dog → cog という最短の変換シーケンスが存在するためです。

解法のアプローチ

この問題は幅優先探索（BFS）を使うことで効率的に解けます。全体の手順は以下の通りです。

• putStar という補助メソッドを定義します。引数 j（位置）と文字列 s を受け取り、s の j 番目の文字を「*」に置き換えた文字列を返します。これにより、「1文字違い」の単語をパターンとしてグループ化できるようになります。
• temp を空文字列として初期化します。
• i を 0 から s のサイズ − 1 まで繰り返します。
  • i == j の場合は temp に「*」を連結し、それ以外の場合は s[i] を連結します。
• メインメソッド ladderLength は、文字列 b（開始語）、文字列 e（終了語）、単語リスト w を受け取ります。
• e が w に存在しない場合、または b・e・w のいずれかが空の場合は 0 を返します。
• キーが文字列型、値が配列型のマップ m を定義します。ここには「* を挿入したパターン → そのパターンに一致する単語群」を格納します。
• i を 0 から w のサイズまで繰り返します。
  • x := w[i]
  • j を 0 から x のサイズまで繰り返します。
    • inter := putStar(j, x)
    • m[inter] に x を追加します。
• キュー q を定義し、ペア (b, 1) を挿入します。ペアの第2要素は現在の変換レベル（シーケンスの長さ）です。
• 訪問済み単語を記録するためのマップ visited を作成します。
• q が空でない間、以下を繰り返します。
  • s := q の先頭ペアを取得し、先頭要素を削除します。
  • x := ペアの第1要素（現在の単語）、l := ペアの第2要素（現在のレベル）
  • i を 0 から x のサイズまで繰り返します。
    • temp := putStar(i, x)
    • j を 0 から m[temp] のサイズまで繰り返します。
      • aa := m[temp][j]
      • aa が e と等しければ l + 1 を返します（最短距離が確定）。
      • visited[aa] が未設定なら、ペア (aa, l + 1) をキューに挿入し、visited[aa] = 1 を設定します。
• キューが空になっても endWord に到達できなければ、0 を返します。

なぜBFSが有効なのか

この問題はグラフの最短経路問題として捉えることができます。各単語をノードとみなし、1文字だけ異なる単語同士をエッジで結んだグラフを考えると、beginWord から endWord までの最短経路を求める問題に帰着します。BFS はレベル（変換回数）ごとに探索を進めるため、初めて endWord に到達した時点のレベルがそのまま答えになります。

計算量

時間計算量は O(N × L) です。ここで N は単語リストの単語数、L は各単語の長さを表します。各単語について L 個のパターン（* を挿入したもの）を生成する必要があるためです。空間計算量も同様に O(N × L) となります。

実装例

以下のC++コードを見ると、より理解が深まるでしょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    string putStar(int j, string s){
        string temp = "";
        for(int i = 0; i < s.size(); i++){
            if(i == j)temp += "*";
            else temp += s[i];
        }
        return temp;
    }
    int ladderLength(string b, string e, vector<string>& w) {
        if(find(w.begin(), w.end(), e) == w.end() || !b.size() || !e.size() || !w.size())return 0;
        map < string , vector <string> > m;
        for(int i = 0; i < w.size(); i++){
            string x = w[i];
            for(int j = 0; j < x.size(); j++){
                string inter = putStar(j,x);
                m[inter].push_back(x);
            }
        }
        queue < pair <string, int> > q;
        q.push({b, 1});
        map <string, int> visited;
        while(!q.empty()){
            pair < string, int > s = q.front();
            q.pop();
            string x = s.first;
            int l = s.second;
            for(int i = 0; i < x.size(); i++){
                string temp = putStar(i ,x);
                for(int j = 0; j < m[temp].size(); j++){
                    string aa = m[temp][j];
                    if(aa == e)return l+1;
                    if(!visited[aa]){
                        q.push({aa, l+1});
                        visited[aa] = 1;
                    }
                }
            }
        }
        int level = 0;
        return 0;
    }
};
main(){
    vector<string> v = {"hot","dot","dog","lot","log","cog"};
    Solution ob;
    cout << (ob.ladderLength("hit", "cog", v));
}

入力

"hit"
"cog"
["hot","dot","dog","lot","log","cog"]

出力

5