Leetcode 126：单词接龙（超详细的解法！！！）

给定两个单词（beginWord和endWord）和一个字典wordList，找出所有从beginWord到endWord的最短转换序列。转换需遵循如下规则：

1. 每次转换只能改变一个字母。
2. 转换过程中的中间单词必须是字典中的单词。

说明:

• 如果不存在这样的转换序列，返回一个空列表。
• 所有单词具有相同的长度。
• 所有单词只由小写字母组成。
• 字典中不存在重复的单词。
• 你可以假设beginWord和endWord是非空的，且二者不相同。

示例 1:

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

输出:
[
  ["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]
]
1
2
3
4
5
6
7
8
9
10

示例 2:

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

输出: []

解释: endWord "cog" 不在字典中，所以不存在符合要求的转换序列。
1
2
3
4
5
6
7
8

解题思路

这个问题是之前问题Leetcode 127：单词接龙（最详细的解法！！！）的提高，首先不难想到一个解法，就是先通过之前问题找到最短路径step，然后通过dfs去找路径长度是step并且起始位置是beginWord终点位置是endWord的路径即可。

    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
        wordDict = collections.defaultdict(list)
        for word in wordList:
            for i in range(len(word)):
                tmp = word[:i] + "_" + word[i+1:]
                wordDict[tmp].append(word)
        
        q, visited, st = [(beginWord, 1)], set(), 0
        while q:
            word, step = q.pop(0)
            if word not in visited:
                visited.add(word)
                if word == endWord:
                    st = step
                    break
                for i in range(len(word)):
                    tmp = word[:i] + "_" + word[i+1:]
                    for neigh in wordDict[tmp]:
                        q.append((neigh, step + 1))
        
        res, visited = [], set([beginWord])
        def dfs(s, w, ws):
            if s == st - 1:  
                if w == endWord:
                    res.append(ws[::])
                return 
            
            for i in range(len(w)):
                tmp = w[:i] + "_" + w[i+1:]
                for neigh in wordDict[tmp]:
                    if neigh not in visited:
                        visited.add(neigh)
                        dfs(s + 1, neigh, ws + [neigh])
                        visited.remove(neigh)
            
        dfs(0, beginWord, [beginWord])
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

但是上面这种解法超时了，所以我们只能通过空间换时间，怎么做？就是在bfs的过程中将所有的路径记录下来（到当前单词的全部最短路径）。怎么记录？通过字典，key记录当前的单词，value记录全部路径。怎么更新？遍历前一个单词（从前一个单词变换到当前单词）的所有路径，将当前单词插入路径结尾即可，并且将当前单词记录到字典中，已被后续使用。

class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
        wordDict = collections.defaultdict(list)
        for word in wordList:
            for i in range(len(word)):
                tmp = word[:i] + "_" + word[i+1:]
                wordDict[tmp].append(word)
        
        q = collections.defaultdict(list)
        q[beginWord].append([beginWord])
        visited, res = set(), []
        while len(q):
            nq = collections.defaultdict(list) 
            for k, v in q.items():
                if k == endWord:
                    return v
                if k not in visited:
                    visited.add(k)
                    for i in range(len(k)):
                        tmp = k[:i] + "_" + k[i+1:]
                        for neigh in wordDict[tmp]:
                            nq[neigh] += [j + [neigh] for j in v]# 这里
            q = nq
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

上面注释那行的代码就是最关键的操作，该操作类似于Leetcode 78：子集（最详细的解法！！！）中的第一种解法思路。

和之前一样，这个问题也可以使用双向bfs，而且速度非常块。双向bfs的实现稍微复杂一些，大家可以参考我的代码：

from collections import defaultdict
class Solution:
    def findLadders(self, beginWord, endWord, wordList):
        wordDict, res = set(wordList), []
        if endWord not in wordDict:
            return res

        s1, s2, step = defaultdict(list), defaultdict(list), 2
        s1[beginWord].append([beginWord])
        s2[endWord].append([endWord])
        while s1:
            stack = defaultdict(list)
            wordDict -= s1.keys()

            for w, paths in s1.items():
                for i in range(len(w)):
                    for j in string.ascii_lowercase:
                        tmp = w[:i] + j + w[i+1:]
                        if tmp not in wordDict:
                            continue
                        if tmp in s2:
                            if paths[0][0] == beginWord:
                                res += [f + b[::-1] for f in paths for b in s2[tmp]]
                            else:
                                res += [b + f[::-1] for f in paths for b in s2[tmp]]
                        stack[tmp] += [p + [tmp] for p in paths]
            
            if len(stack) < len(s2):
                s1 = stack
            else:
                s1, s2 = s2, stack
            step += 1
            if res and step > len(res[0]):
                return res
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题，希望大家指出！！！