按字典 wordList 完成从单词 beginWord 到单词 endWord 转化，一个表示此过程的 转换序列 是形式上像 beginWord -> s1 -> s2 -> ... -> sk 这样的单词序列，并满足：
- 每对相邻的单词之间仅有单个字母不同。
- 转换过程中的每个单词
si（1 <= i <= k）必须是字典wordList中的单词。注意，beginWord不必是字典wordList中的单词。 sk == endWord
给你两个单词 beginWord 和 endWord ，以及一个字典 wordList 。请你找出并返回所有从 beginWord 到 endWord 的 最短转换序列 ，如果不存在这样的转换序列，返回一个空列表。每个序列都应该以单词列表 [beginWord, s1, s2, ..., sk] 的形式返回。
示例 1：
输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] 输出：[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]] 解释：存在 2 种最短的转换序列： "hit" -> "hot" -> "dot" -> "dog" -> "cog" "hit" -> "hot" -> "lot" -> "log" -> "cog"
示例 2：
输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"] 输出：[] 解释：endWord "cog" 不在字典 wordList 中，所以不存在符合要求的转换序列。
提示：
1 <= beginWord.length <= 5endWord.length == beginWord.length1 <= wordList.length <= 500wordList[i].length == beginWord.lengthbeginWord、endWord和wordList[i]由小写英文字母组成beginWord != endWordwordList中的所有单词 互不相同
DFS。
class Solution:
def findLadders(
self, beginWord: str, endWord: str, wordList: List[str]
) -> List[List[str]]:
def dfs(path, cur):
if cur == beginWord:
ans.append(path[::-1])
return
for precursor in prev[cur]:
path.append(precursor)
dfs(path, precursor)
path.pop()
ans = []
words = set(wordList)
if endWord not in words:
return ans
words.discard(beginWord)
dist = {beginWord: 0}
prev = defaultdict(set)
q = deque([beginWord])
found = False
step = 0
while q and not found:
step += 1
for i in range(len(q), 0, -1):
p = q.popleft()
s = list(p)
for i in range(len(s)):
ch = s[i]
for j in range(26):
s[i] = chr(ord('a') + j)
t = ''.join(s)
if dist.get(t, 0) == step:
prev[t].add(p)
if t not in words:
continue
prev[t].add(p)
words.discard(t)
q.append(t)
dist[t] = step
if endWord == t:
found = True
s[i] = ch
if found:
path = [endWord]
dfs(path, endWord)
return ansclass Solution {
private List<List<String>> ans;
private Map<String, Set<String>> prev;
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
ans = new ArrayList<>();
Set<String> words = new HashSet<>(wordList);
if (!words.contains(endWord)) {
return ans;
}
words.remove(beginWord);
Map<String, Integer> dist = new HashMap<>();
dist.put(beginWord, 0);
prev = new HashMap<>();
Queue<String> q = new ArrayDeque<>();
q.offer(beginWord);
boolean found = false;
int step = 0;
while (!q.isEmpty() && !found) {
++step;
for (int i = q.size(); i > 0; --i) {
String p = q.poll();
char[] chars = p.toCharArray();
for (int j = 0; j < chars.length; ++j) {
char ch = chars[j];
for (char k = 'a'; k <= 'z'; ++k) {
chars[j] = k;
String t = new String(chars);
if (dist.getOrDefault(t, 0) == step) {
prev.get(t).add(p);
}
if (!words.contains(t)) {
continue;
}
prev.computeIfAbsent(t, key -> new HashSet<>()).add(p);
words.remove(t);
q.offer(t);
dist.put(t, step);
if (endWord.equals(t)) {
found = true;
}
}
chars[j] = ch;
}
}
}
if (found) {
Deque<String> path = new ArrayDeque<>();
path.add(endWord);
dfs(path, beginWord, endWord);
}
return ans;
}
private void dfs(Deque<String> path, String beginWord, String cur) {
if (cur.equals(beginWord)) {
ans.add(new ArrayList<>(path));
return;
}
for (String precursor : prev.get(cur)) {
path.addFirst(precursor);
dfs(path, beginWord, precursor);
path.removeFirst();
}
}
}func findLadders(beginWord string, endWord string, wordList []string) [][]string {
var ans [][]string
words := make(map[string]bool)
for _, word := range wordList {
words[word] = true
}
if !words[endWord] {
return ans
}
words[beginWord] = false
dist := map[string]int{beginWord: 0}
prev := map[string]map[string]bool{}
q := []string{beginWord}
found := false
step := 0
for len(q) > 0 && !found {
step++
for i := len(q); i > 0; i-- {
p := q[0]
q = q[1:]
chars := []byte(p)
for j := 0; j < len(chars); j++ {
ch := chars[j]
for k := 'a'; k <= 'z'; k++ {
chars[j] = byte(k)
t := string(chars)
if v, ok := dist[t]; ok {
if v == step {
prev[t][p] = true
}
}
if !words[t] {
continue
}
if len(prev[t]) == 0 {
prev[t] = make(map[string]bool)
}
prev[t][p] = true
words[t] = false
q = append(q, t)
dist[t] = step
if endWord == t {
found = true
}
}
chars[j] = ch
}
}
}
var dfs func(path []string, begin, cur string)
dfs = func(path []string, begin, cur string) {
if cur == beginWord {
cp := make([]string, len(path))
copy(cp, path)
ans = append(ans, cp)
return
}
for k := range prev[cur] {
path = append([]string{k}, path...)
dfs(path, beginWord, k)
path = path[1:]
}
}
if found {
path := []string{endWord}
dfs(path, beginWord, endWord)
}
return ans
}