126. 单词接龙 II

题目描述

输入起始词 beginWord、目标词 endWord 和单词表 wordList，所有单词长度相同。

从 beginWord 开始，每一步把当前单词恰好改动一个字母，得到下一个单词。每一步得到的单词都必须在 wordList 里，而 beginWord 本身可以不在。最后一步得到的单词必须是 endWord。

找出所有步数最少的变换过程。每个过程写成从 beginWord 到 endWord 依次经过的单词列表。返回这些列表，顺序不限；若无法到达 endWord，返回 []。

示例 1

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]

解释：最短变换需要 4 步，恰好有两条：经过 dot、dog 或经过 lot、log。

示例 2

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：[]

解释：cog 不在单词表中，无法到达。

数据范围

1 <= beginWord.length <= 5
endWord.length == beginWord.length
1 <= wordList.length <= 500
wordList[i].length == beginWord.length
所有单词只含小写英文字母。
beginWord != endWord
wordList 中没有重复单词。

解题思路

分两步。第一步按层 BFS：先把当前层的单词从字典里删掉（保证只往更深的层走），再对每个单词枚举改一个字母的所有结果，在字典里的就进入下一层，并记录它的父节点（可能有多个）。一旦某层出现 endWord 就停止。第二步从 endWord 沿父节点回溯到 beginWord，把路径翻转后就是一条最短序列。

为什么正确

parents[x] 中的每个单词都在 x 的上一层，所以沿 parents 从 endWord 走回 beginWord 的任意路径长度都等于最短距离。

复杂度分析

设字典大小 N、单词长 L，BFS 为 O(N · 26 · L²)；回溯与答案数量成正比。

易错点

不能在发现邻居时立刻从字典删除它，否则同层其他单词无法再把它记为子节点，会漏掉部分最短路径；应当在整层开始前统一删除。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
        words = set(wordList)
        if endWord not in words:
            return []
        parents = {beginWord: []}
        layer = [beginWord]
        found = False
        while layer and not found:
            nxt = {}
            for w in layer:
                words.discard(w)
            for w in layer:
                for i in range(len(w)):
                    for c in 'abcdefghijklmnopqrstuvwxyz':
                        nw = w[:i] + c + w[i + 1:]
                        if nw in words:
                            nxt.setdefault(nw, []).append(w)
                            if nw == endWord:
                                found = True
            parents.update(nxt)
            layer = list(nxt)
        res, path = [], [endWord]

        def dfs(w):
            if w == beginWord:
                res.append(path[::-1])
                return
            for p in parents[w]:
                path.append(p)
                dfs(p)
                path.pop()

        if found:
            dfs(endWord)
        return res

class Solution {
    Map<String, List<String>> parents = new HashMap<>();
    List<List<String>> res = new ArrayList<>();
    List<String> path = new ArrayList<>();
    String beginWord;

    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        Set<String> words = new HashSet<>(wordList);
        if (!words.contains(endWord)) {
            return res;
        }
        this.beginWord = beginWord;
        parents.put(beginWord, new ArrayList<>());
        List<String> layer = new ArrayList<>();
        layer.add(beginWord);
        boolean found = false;
        while (!layer.isEmpty() && !found) {
            Map<String, List<String>> nxt = new LinkedHashMap<>();
            for (String w : layer) {
                words.remove(w);
            }
            for (String w : layer) {
                for (int i = 0; i < w.length(); i++) {
                    for (char c = 'a'; c <= 'z'; c++) {
                        String nw = w.substring(0, i) + c + w.substring(i + 1);
                        if (words.contains(nw)) {
                            nxt.computeIfAbsent(nw, k -> new ArrayList<>()).add(w);
                            if (nw.equals(endWord)) {
                                found = true;
                            }
                        }
                    }
                }
            }
            parents.putAll(nxt);
            layer = new ArrayList<>(nxt.keySet());
        }
        path.add(endWord);
        if (found) {
            dfs(endWord);
        }
        return res;
    }

    void dfs(String w) {
        if (w.equals(beginWord)) {
            List<String> one = new ArrayList<>(path);
            Collections.reverse(one);
            res.add(one);
            return;
        }
        for (String p : parents.get(w)) {
            path.add(p);
            dfs(p);
            path.remove(path.size() - 1);
        }
    }
}

class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> words(wordList.begin(), wordList.end());
        if (!words.count(endWord)) {
            return {};
        }
        unordered_map<string, vector<string>> parents;
        parents[beginWord] = {};
        vector<string> layer = {beginWord};
        bool found = false;
        while (!layer.empty() && !found) {
            unordered_map<string, vector<string>> nxt;
            for (auto& w : layer) {
                words.erase(w);
            }
            for (auto& w : layer) {
                for (int i = 0; i < (int)w.size(); i++) {
                    for (char c = 'a'; c <= 'z'; c++) {
                        string nw = w.substr(0, i) + c + w.substr(i + 1);
                        if (words.count(nw)) {
                            nxt[nw].push_back(w);
                            if (nw == endWord) {
                                found = true;
                            }
                        }
                    }
                }
            }
            layer.clear();
            for (auto& [k, v] : nxt) {
                parents[k] = v;
                layer.push_back(k);
            }
        }
        vector<vector<string>> res;
        vector<string> path = {endWord};
        function<void(const string&)> dfs = [&](const string& w) {
            if (w == beginWord) {
                res.push_back(vector<string>(path.rbegin(), path.rend()));
                return;
            }
            for (auto& p : parents[w]) {
                path.push_back(p);
                dfs(p);
                path.pop_back();
            }
        };
        if (found) {
            dfs(endWord);
        }
        return res;
    }
};

func findLadders(beginWord string, endWord string, wordList []string) [][]string {
	words := map[string]bool{}
	for _, w := range wordList {
		words[w] = true
	}
	if !words[endWord] {
		return [][]string{}
	}
	parents := map[string][]string{beginWord: {}}
	layer := []string{beginWord}
	found := false
	for len(layer) > 0 && !found {
		nxt := map[string][]string{}
		order := []string{}
		for _, w := range layer {
			delete(words, w)
		}
		for _, w := range layer {
			for i := 0; i < len(w); i++ {
				for c := byte('a'); c <= 'z'; c++ {
					nw := w[:i] + string(c) + w[i+1:]
					if words[nw] {
						if _, ok := nxt[nw]; !ok {
							order = append(order, nw)
						}
						nxt[nw] = append(nxt[nw], w)
						if nw == endWord {
							found = true
						}
					}
				}
			}
		}
		for k, v := range nxt {
			parents[k] = v
		}
		layer = order
	}
	res, path := [][]string{}, []string{endWord}
	var dfs func(w string)
	dfs = func(w string) {
		if w == beginWord {
			one := make([]string, len(path))
			for i, x := range path {
				one[len(path)-1-i] = x
			}
			res = append(res, one)
			return
		}
		for _, p := range parents[w] {
			path = append(path, p)
			dfs(p)
			path = path[:len(path)-1]
		}
	}
	if found {
		dfs(endWord)
	}
	return res
}

var findLadders = function(beginWord, endWord, wordList) {
    const words = new Set(wordList);
    if (!words.has(endWord)) {
        return [];
    }
    const parents = new Map([[beginWord, []]]);
    let layer = [beginWord];
    let found = false;
    while (layer.length && !found) {
        const nxt = new Map();
        for (const w of layer) {
            words.delete(w);
        }
        for (const w of layer) {
            for (let i = 0; i < w.length; i++) {
                for (let c = 97; c <= 122; c++) {
                    const nw = w.slice(0, i) + String.fromCharCode(c) + w.slice(i + 1);
                    if (words.has(nw)) {
                        if (!nxt.has(nw)) nxt.set(nw, []);
                        nxt.get(nw).push(w);
                        if (nw === endWord) {
                            found = true;
                        }
                    }
                }
            }
        }
        for (const [k, v] of nxt) parents.set(k, v);
        layer = [...nxt.keys()];
    }
    const res = [], path = [endWord];
    const dfs = (w) => {
        if (w === beginWord) {
            res.push([...path].reverse());
            return;
        }
        for (const p of parents.get(w)) {
            path.push(p);
            dfs(p);
            path.pop();
        }
    };
    if (found) {
        dfs(endWord);
    }
    return res;
};

function findLadders(beginWord: string, endWord: string, wordList: string[]): string[][] {
    const words = new Set(wordList);
    if (!words.has(endWord)) {
        return [];
    }
    const parents = new Map<string, string[]>([[beginWord, []]]);
    let layer = [beginWord];
    let found = false;
    while (layer.length && !found) {
        const nxt = new Map<string, string[]>();
        for (const w of layer) {
            words.delete(w);
        }
        for (const w of layer) {
            for (let i = 0; i < w.length; i++) {
                for (let c = 97; c <= 122; c++) {
                    const nw = w.slice(0, i) + String.fromCharCode(c) + w.slice(i + 1);
                    if (words.has(nw)) {
                        if (!nxt.has(nw)) nxt.set(nw, []);
                        nxt.get(nw)!.push(w);
                        if (nw === endWord) {
                            found = true;
                        }
                    }
                }
            }
        }
        for (const [k, v] of nxt) parents.set(k, v);
        layer = [...nxt.keys()];
    }
    const res: string[][] = [], path: string[] = [endWord];
    const dfs = (w: string): void => {
        if (w === beginWord) {
            res.push([...path].reverse());
            return;
        }
        for (const p of parents.get(w)!) {
            path.push(p);
            dfs(p);
            path.pop();
        }
    };
    if (found) {
        dfs(endWord);
    }
    return res;
}

载入编辑器，自己跑一遍 →

回溯专题的其他题目

查看回溯全部题目 →