title
按字典 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 <= 5000wordList[i].length == beginWord.lengthbeginWord、endWord和wordList[i]由小写英文字母组成beginWord != endWordwordList中的所有单词 互不相同
solution
class Solution:
def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
word_set = set(wordList)
word_set.add(beginWord)
import collections
graph = collections.defaultdict(list)
for w in word_set:
wl = list(w)
for i in range(len(wl)):
old = w[i]
for k in range(ord('a'), ord('z') + 1, 1):
c = chr(k)
if c == old: continue
wl[i] = c
nxt = "".join(wl)
if nxt in word_set:
graph[w].append(nxt)
wl[i] = old
import collections
q = collections.deque()
q.append(beginWord)
pre = collections.defaultdict(set)
dis = {}
dis[beginWord] = 0
while q:
nxt_nodes = set()
for _ in range(len(q)):
u = q.popleft()
for v in graph[u]:
if v in dis: continue
pre[v].add(u)
nxt_nodes.add(v)
for v in nxt_nodes:
dis[v] = dis[u] + 1
q.append(v)
# print(pre)
# print(dis)
ans = []
def dfs(node, path: list):
path.append(node)
if node == beginWord:
nonlocal ans
ans.append(list(path[::-1]))
path.pop()
return
for u in pre[node]:
dfs(u, path)
path.pop()
dfs(endWord, [])
# print(ans)
return ans