【Python】1文字ずつ変更して別の単語へ到達する最小ステップ数を求めるプログラム

問題の概要

単語のリスト「dictionary」と、2つの文字列「start」「end」が与えられます。startからendへ向かって、一度に1文字だけ変更しながら到達することを目指します。ただし、途中で作られるすべての単語はdictionaryに含まれている必要があり、大文字と小文字は区別されます。このとき、endに到達するまでに必要な最小ステップ数を求めます。到達が不可能な場合は-1を返します。

例えば、dictionary = ["may", "ray", "rat"]、start = "rat"、end = "may" の場合、出力は3になります。「rat → ray → may」というパスを選べば、3ステップで目的の単語に到達できるためです。

解き方：幅優先探索（BFS）を使う

この種の「最短手数を求める」問題は、幅優先探索（BFS）が最適です。BFSは開始地点から近い順に状態を展開していくため、最初にendに到達した時点の手数が必ず最小値になります。

具体的な手順は以下の通りです。

1. dictionaryを重複のないセット（set）に変換します。これにより、存在確認と削除を高速に行えます。
2. (start, 1) というペアを持つ両端キュー（deque）を用意します。第2要素は現在までの手数です。
3. キューが空になるまで次を繰り返します。
   • キューの左端から (word, distance) を取り出します。
   • wordがendと一致していれば、distanceを答えとして返します。
   • wordの各位置 i について、アルファベット26文字それぞれの文字 c で置き換えた next_word = word[:i] + c + word[i+1:] を生成します。
   • next_wordがdictionaryに存在する場合は、dictionaryから削除（訪問済みマークの代わり）し、(next_word, distance + 1) をキューの末尾に追加します。
4. キューが空になってもendに到達できなければ、-1を返します。

訪問済みの単語をdictionaryから削除しておくことで、同じ単語を何度も処理する無駄を防ぎ、無限ループも回避できます。

Pythonでの実装例

以下が実際の実装コードです。

from collections import deque
class Solution:
    def solve(self, dictionary, start, end):
        dictionary = set(dictionary)
        q = deque([(start, 1)])
        while q:
            word, distance = q.popleft()
            if word == end:
                return distance
            for i in range(len(word)):
                for c in "abcdefghijklmnopqrstuvwxyz":
                    next_word = word[:i] + c + word[i + 1 :]
                    if next_word in dictionary:
                        dictionary.remove(next_word)
                        q.append((next_word, distance + 1))
        return -1
ob = Solution()
dictionary = ["may", "ray", "rat"]
start = "rat"
end = "may"
print(ob.solve(dictionary, start, end))

入力

["may", "ray", "rat"], "rat", "may"

出力

3

計算量について

単語の長さをL、辞書の単語数をNとすると、各単語につき L × 26 個の候補を生成するため、時間計算量はおおよそ O(N × L × 26) となります。セットによる存在確認がO(1)で行える点が、この実装の効率化のポイントです。