20. Word Ladder

読了目安約2分

Graph / LeetCode 127 (Hard) — 1 文字違いの単語をたどる BFS で最短の変換手数を求める。

この章の目次

問題

LeetCode 127. Word Ladder（Hard / カテゴリ: Graph）

開始単語 beginWord、目標単語 endWord、単語の一覧 wordList が与えられます。 1 回の変換では 1 文字だけ変えられ、変換後の単語は wordList に含まれていなければなりません。 beginWord から endWord に至る最短の変換列の長さを、beginWord を含む単語数で返します。到達できなければ 0 を返します。

Arai60 の中では最も難しい部類の問題です。

考え方

ヒント 1

単語を頂点、1 文字違いの関係を辺とみなすと、これはグラフの最短経路の問題です。辺に重みがない最短経路は幅優先探索（BFS）で求まります。

ヒント 2

隣の単語は、各位置の文字を a から z に置き換えた候補が一覧にあるかで列挙します。見つけた単語を集合（Set）から削除していけば、訪問済みの管理を兼ねられます。 BFS は同じ手数の単語のまとまり（層）ごとに進め、層が進むたびに手数を 1 増やします。

Swift 実装のポイント

wordList は Set<String> に変換します。候補の存在チェックが平均 O(1) になります。
1 文字の置き換えは var chars = Array(word) で [Character] にしてから行い、String(chars) で戻します。
発見した単語はその場で集合から削除します。再訪問の防止と訪問済み管理の省略を兼ねます。
探索の前に endWord が集合になければ、0 を返して打ち切ります。

模範解答

Swift
class Solution {
    func ladderLength(_ beginWord: String, _ endWord: String, _ wordList: [String]) -> Int {
        var dict = Set(wordList)
        guard dict.contains(endWord) else { return 0 }
        dict.remove(beginWord)
        let letters = Array("abcdefghijklmnopqrstuvwxyz")
        var queue = [beginWord]
        var steps = 1
        while !queue.isEmpty {
            var next: [String] = []
            for word in queue {
                if word == endWord { return steps }
                var chars = Array(word)
                for i in 0..<chars.count {
                    let original = chars[i]
                    for letter in letters where letter != original {
                        chars[i] = letter
                        let candidate = String(chars)
                        if dict.contains(candidate) {
                            dict.remove(candidate)
                            next.append(candidate)
                        }
                    }
                    chars[i] = original
                }
            }
            queue = next
            steps += 1
        }
        return 0
    }
}

計算量: O(26 L N)（N は単語数、L は単語の長さ。各単語につき 26L 個の候補を試します）。