127. 单词接龙
题目描述
输入起始词 beginWord、目标词 endWord 和单词表 wordList，所有单词长度相同。
从 beginWord 开始，每一步只改动当前单词的一个字母。每一步得到的单词都必须在 wordList 里，beginWord 本身可以不在。最后要得到 endWord。
返回最短变换序列中的单词个数，首尾两个单词都要计入。无法到达时返回 0。
示例 1
输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] 输出：5
解释：例如 hit -> hot -> dot -> dog -> cog，共 5 个单词。
示例 2
输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"] 输出：0
解释：cog 不在单词表中，无法到达。
数据范围
1 <= beginWord.length <= 10endWord.length == beginWord.length1 <= wordList.length <= 5000wordList[i].length == beginWord.length- 所有单词只含小写英文字母。
beginWord != endWordwordList中没有重复单词。
解题思路：单向广度优先搜索
把每个词看成图的节点，只差一个字母的两个词之间有边。求无权图的最短路，用 BFS。找邻居时不建图，而是枚举每个位置换成 26 个字母，再查集合。第一次弹出 endWord 时的步数就是答案。
为什么正确
队列中的 steps 单调不减；一个词在入队时就加入 seen，所以它的 steps 就是从起点到它的最短距离。
复杂度分析
时间 O(N · L · 26 · L)，N 为词数，L 为词长；空间 O(N · L)。
易错点
要在入队时就标记 seen，而不是出队时。否则同一个词会被重复入队很多次，大数据会超时。另外 endWord 不在列表中时要直接返回 0。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
words = set(wordList)
if endWord not in words:
return 0
queue = collections.deque([(beginWord, 1)])
seen = {beginWord}
while queue:
word, steps = queue.popleft()
if word == endWord:
return steps
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
nxt = word[:i] + c + word[i + 1:]
if nxt in words and nxt not in seen:
seen.add(nxt)
queue.append((nxt, steps + 1))
return 0class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> words = new HashSet<>(wordList);
if (!words.contains(endWord)) {
return 0;
}
Deque<Object[]> queue = new ArrayDeque<>();
queue.offer(new Object[]{beginWord, 1});
Set<String> seen = new HashSet<>(List.of(beginWord));
while (!queue.isEmpty()) {
Object[] cur = queue.poll();
String word = (String) cur[0];
int steps = (int) cur[1];
if (word.equals(endWord)) {
return steps;
}
for (int i = 0; i < word.length(); i++) {
for (char c = 'a'; c <= 'z'; c++) {
String nxt = word.substring(0, i) + c + word.substring(i + 1);
if (words.contains(nxt) && !seen.contains(nxt)) {
seen.add(nxt);
queue.offer(new Object[]{nxt, steps + 1});
}
}
}
}
return 0;
}
}class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> words(wordList.begin(), wordList.end());
if (!words.count(endWord)) {
return 0;
}
queue<pair<string, int>> q;
q.push({beginWord, 1});
unordered_set<string> seen = {beginWord};
while (!q.empty()) {
auto [word, steps] = q.front();
q.pop();
if (word == endWord) {
return steps;
}
for (int i = 0; i < (int)word.size(); i++) {
for (char c = 'a'; c <= 'z'; c++) {
string nxt = word.substr(0, i) + c + word.substr(i + 1);
if (words.count(nxt) && !seen.count(nxt)) {
seen.insert(nxt);
q.push({nxt, steps + 1});
}
}
}
}
return 0;
}
};func ladderLength(beginWord string, endWord string, wordList []string) int {
words := map[string]bool{}
for _, w := range wordList {
words[w] = true
}
if !words[endWord] {
return 0
}
type item struct {
word string
steps int
}
queue := []item{{beginWord, 1}}
seen := map[string]bool{beginWord: true}
for len(queue) > 0 {
word, steps := queue[0].word, queue[0].steps
queue = queue[1:]
if word == endWord {
return steps
}
for i := 0; i < len(word); i++ {
for c := byte('a'); c <= 'z'; c++ {
nxt := word[:i] + string(c) + word[i+1:]
if words[nxt] && !seen[nxt] {
seen[nxt] = true
queue = append(queue, item{nxt, steps + 1})
}
}
}
}
return 0
}var ladderLength = function(beginWord, endWord, wordList) {
const words = new Set(wordList);
if (!words.has(endWord)) {
return 0;
}
const queue = [[beginWord, 1]];
const seen = new Set([beginWord]);
let head = 0;
while (head < queue.length) {
const [word, steps] = queue[head++];
if (word === endWord) {
return steps;
}
for (let i = 0; i < word.length; i++) {
for (const c of 'abcdefghijklmnopqrstuvwxyz') {
const nxt = word.slice(0, i) + c + word.slice(i + 1);
if (words.has(nxt) && !seen.has(nxt)) {
seen.add(nxt);
queue.push([nxt, steps + 1]);
}
}
}
}
return 0;
};function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
const words = new Set(wordList);
if (!words.has(endWord)) {
return 0;
}
const queue: [string, number][] = [[beginWord, 1]];
const seen = new Set([beginWord]);
let head = 0;
while (head < queue.length) {
const [word, steps] = queue[head++];
if (word === endWord) {
return steps;
}
for (let i = 0; i < word.length; i++) {
for (const c of 'abcdefghijklmnopqrstuvwxyz') {
const nxt = word.slice(0, i) + c + word.slice(i + 1);
if (words.has(nxt) && !seen.has(nxt)) {
seen.add(nxt);
queue.push([nxt, steps + 1]);
}
}
}
}
return 0;
}其他解法
单向广度优先搜索写法最直接；双向广度优先搜索从两端向中间搜索，分支多时明显更快。
解法 2：双向广度优先搜索 时间 O(N·L·Σ)，空间 O(N·L)
从 beginWord 和 endWord 两端同时按层扩展，各用一个集合保存当前层。每轮只扩展较小的一侧，扩展出的新词从字典中删除。一旦新词出现在另一侧的集合中，说明两端相遇，返回当前步数加 1。
最坏复杂度不变，但搜索半径减半，实际访问的节点数往往少很多。需要维护两个集合并处理交换，写法更复杂。
from typing import List
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
words = set(wordList)
if endWord not in words:
return 0
if beginWord == endWord:
return 1
front, back = {beginWord}, {endWord}
words.discard(beginWord)
words.discard(endWord)
steps = 1
while front and back:
if len(front) > len(back):
front, back = back, front
nxt = set()
for w in front:
for i in range(len(w)):
for c in 'abcdefghijklmnopqrstuvwxyz':
nw = w[:i] + c + w[i + 1:]
if nw in back:
return steps + 1
if nw in words:
words.remove(nw)
nxt.add(nw)
front = nxt
steps += 1
return 0class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> words = new HashSet<>(wordList);
if (!words.contains(endWord)) return 0;
if (beginWord.equals(endWord)) return 1;
Set<String> front = new HashSet<>(), back = new HashSet<>();
front.add(beginWord);
back.add(endWord);
words.remove(beginWord);
words.remove(endWord);
int steps = 1;
while (!front.isEmpty() && !back.isEmpty()) {
if (front.size() > back.size()) {
Set<String> tmp = front;
front = back;
back = tmp;
}
Set<String> nxt = new HashSet<>();
for (String w : front) {
char[] arr = w.toCharArray();
for (int i = 0; i < arr.length; i++) {
char orig = arr[i];
for (char c = 'a'; c <= 'z'; c++) {
arr[i] = c;
String nw = new String(arr);
if (back.contains(nw)) return steps + 1;
if (words.remove(nw)) nxt.add(nw);
}
arr[i] = orig;
}
}
front = nxt;
steps++;
}
return 0;
}
}class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> words(wordList.begin(), wordList.end());
if (!words.count(endWord)) return 0;
if (beginWord == endWord) return 1;
unordered_set<string> front{beginWord}, back{endWord};
words.erase(beginWord);
words.erase(endWord);
int steps = 1;
while (!front.empty() && !back.empty()) {
if (front.size() > back.size()) swap(front, back);
unordered_set<string> nxt;
for (const string& w : front) {
string nw = w;
for (int i = 0; i < (int)nw.size(); i++) {
char orig = nw[i];
for (char c = 'a'; c <= 'z'; c++) {
nw[i] = c;
if (back.count(nw)) return steps + 1;
if (words.count(nw)) {
words.erase(nw);
nxt.insert(nw);
}
}
nw[i] = orig;
}
}
front = move(nxt);
steps++;
}
return 0;
}
};func ladderLength(beginWord string, endWord string, wordList []string) int {
words := map[string]bool{}
for _, w := range wordList {
words[w] = true
}
if !words[endWord] {
return 0
}
if beginWord == endWord {
return 1
}
front := map[string]bool{beginWord: true}
back := map[string]bool{endWord: true}
delete(words, beginWord)
delete(words, endWord)
steps := 1
for len(front) > 0 && len(back) > 0 {
if len(front) > len(back) {
front, back = back, front
}
nxt := map[string]bool{}
for w := range front {
arr := []byte(w)
for i := range arr {
orig := arr[i]
for c := byte('a'); c <= 'z'; c++ {
arr[i] = c
nw := string(arr)
if back[nw] {
return steps + 1
}
if words[nw] {
delete(words, nw)
nxt[nw] = true
}
}
arr[i] = orig
}
}
front = nxt
steps++
}
return 0
}var ladderLength = function(beginWord, endWord, wordList) {
const words = new Set(wordList);
if (!words.has(endWord)) return 0;
if (beginWord === endWord) return 1;
let front = new Set([beginWord]), back = new Set([endWord]);
words.delete(beginWord);
words.delete(endWord);
let steps = 1;
while (front.size && back.size) {
if (front.size > back.size) [front, back] = [back, front];
const nxt = new Set();
for (const w of front) {
for (let i = 0; i < w.length; i++) {
for (let k = 0; k < 26; k++) {
const nw = w.slice(0, i) + String.fromCharCode(97 + k) + w.slice(i + 1);
if (back.has(nw)) return steps + 1;
if (words.has(nw)) {
words.delete(nw);
nxt.add(nw);
}
}
}
}
front = nxt;
steps++;
}
return 0;
};function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
const words = new Set<string>(wordList);
if (!words.has(endWord)) return 0;
if (beginWord === endWord) return 1;
let front = new Set<string>([beginWord]), back = new Set<string>([endWord]);
words.delete(beginWord);
words.delete(endWord);
let steps = 1;
while (front.size && back.size) {
if (front.size > back.size) [front, back] = [back, front];
const nxt = new Set<string>();
for (const w of front) {
for (let i = 0; i < w.length; i++) {
for (let k = 0; k < 26; k++) {
const nw = w.slice(0, i) + String.fromCharCode(97 + k) + w.slice(i + 1);
if (back.has(nw)) return steps + 1;
if (words.has(nw)) {
words.delete(nw);
nxt.add(nw);
}
}
}
}
front = nxt;
steps++;
}
return 0;
}