C++で解く「単語の梯子（ワードラダー）」問題：ターゲット単語に到達する最短チェーンの長さ

この問題では、辞書と2つの単語「スタート（start）」と「ターゲット（target）」が与えられます。目的は、スタート単語からターゲット単語へと到達する「単語の梯子（ワードラダー）」と呼ばれるチェーンを生成することです。チェーンを構成する各単語は、隣り合う単語とたった1文字だけ異なり、かつすべて辞書に存在しなければなりません。なお、ターゲット単語は辞書に含まれており、すべての単語の長さは同一であるとします。プログラムの出力として、スタートからターゲットまでの最短経路の長さを求めます。

まずは具体例を見ながら、問題の内容を確認しましょう。

入力例

Dictionary = {'HEAL', 'HATE', 'HEAT', 'TEAT', 'THAT', 'WHAT', 'HAIL', 'THAE'}
Start = 'HELL'
Target = 'THAE'

出力例

6

解説

HELL → HEAL → HEAT → TEAT → THAT → THAE

上記の例では、「HELL」を出発点として、各ステップで1文字だけ変更しながら進み、6段階目でターゲットである「THAE」に到達しています。これが最短のチェーンとなり、答えは6です。

解決のアプローチ

この問題を解くには、幅優先探索（BFS）を利用します。辞書内の単語に対して幅優先探索を実行し、直前の単語から1文字だけ異なる単語をレベルごとに順番に見つけていくことで、スタートからターゲットへの梯子（チェーン）を構築できます。

アルゴリズムのポイント

• BFSはチェーンの長さ（レベル）ごとに探索を進めるため、最初にターゲットへ到達した時点の経路が自動的に最短経路になります。
• 一度キューに追加した単語は辞書から削除することで、同じ単語を繰り返し探索する無駄を防いでいます。
• 各文字の位置について「a」～「z」の26文字を試すため、計算量は O(N × L × 26)、つまり約 O(N × L) です（Nは辞書内の単語数、Lは単語の長さ）。

それでは、この解法を実装したC++プログラムを見てみましょう。

実装例

#include <bits/stdc++.h>
using namespace std;
int wordLadder(string start, string target, set<string>& dictionary) {
   if (dictionary.find(target) == dictionary.end())
   return 0;
   int level = 0, wordlength = start.size();
   queue<string> ladder;
   ladder.push(start);
   while (!ladder.empty()) {
      ++level;
      int sizeOfLadder = ladder.size();
      for (int i = 0; i < sizeOfLadder; ++i) {
         string word = ladder.front();
         ladder.pop();
         for (int pos = 0; pos < wordlength; ++pos) {
            char orig_char = word[pos];
            for (char c = 'a'; c <= 'z'; ++c) {
               word[pos] = c;
               if (word == target)
                  return level + 1;
               if (dictionary.find(word) == dictionary.end())
                  continue;
               dictionary.erase(word);
               ladder.push(word);
            }
            word[pos] = orig_char;
         }
      }
   }
   return 0;
}
int main() {
   set<string> dictionary;
   dictionary.insert("heal");
   dictionary.insert("heat");
   dictionary.insert("teat");
   dictionary.insert("that");
   dictionary.insert("what");
   dictionary.insert("thae");
   dictionary.insert("hlle");
   string start = "hell";
   string target = "thae";
   cout<<"Length of shortest chain from '"<<start<<"' to '"<<target<<"' is: "<<wordLadder(start, target, dictionary);
   return 0;
}

出力

Length of shortest chain from 'hell' to 'thae' is: 6

このように、幅優先探索（BFS）を用いることで、1文字ずつ変化させながらターゲット単語へ到達する最短チェーンの長さを効率的に求めることができます。単語変換パズルだけでなく、グラフの最短経路問題全般にも応用できる基本的な手法なので、ぜひマスターしておきましょう。