Given two words (beginWord and endWord), and a dictionary’s word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:
1. Only one letter can be changed at a time
2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
Note:
Return an empty list if there is no such transformation sequence. All words have the same length.
All words contain only lowercase alphabetic characters. You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.
Example 1:
Input:
beginWord = “hit”,
endWord = “cog”,
wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]
Output:
[
[“hit”,”hot”,”dot”,”dog”,”cog”],
[“hit”,”hot”,”lot”,”log”,”cog”]
]
Example 2:
Input:The endWord “cog” is not in wordList, therefore no possibletransformation.
beginWord = “hit”
endWord = “cog”
wordList = [“hot”,”dot”,”dog”,”lot”,”log”]
Output: []
*Explanation:
题目大意:
给定一个字典和两个单词。每次变换一个字母的得到新单词且该词要在字典中。求所有最少的变换路径。
解题思路:
更难于Leetcode 127,BFS用于找最短路径而DFS找路径,此题正是贯彻这一思想,先用BFS找出最短路径,
然后根据最短路径值找出所有路径。找BFS解的同时建图用邻接表表示Map
部分图,与解相关的图)和解集合Map
Dijkistra的图输入和解。DFS从始点开始遍历邻接节点,确保沿着最短路径走,最短路径为
map.get(cur)+1=map.get(next)表示当前节点到始点距离+1=儿节点到始点距离,终止条件为找到目标节点。
- 在遍历所有邻接节点的时候,如果不加筛选对所有邻接节点都做DFS会造成LTE。关键是要利用BFS中所有
节点到单源的最短路径来剪枝。只需DFS最短路径上的节点,否则跳过。 - 利用了单源最短路径映射表distance后,不需要记录visited,因为重复的节点不会在最短路劲上。
- Cache nextWords的结果。
解题步骤:
这题是最短路径题,第一时间想到BFS。这是一条典型的单源最短路径问题。
- 建字典。
- BFS访问,得到图和单源最短路径Map,以及最短路径距离。同时建立邻接表graph[word] = neighbors,DFS时候不用再次找相邻单词
- DFS求路径,按最短路径剪枝dict[neighbor] == dict[startWord] + 1。
注意事项:
- 注意题目条件,开始词不在字典中(终结词默认在,否则无结果),要将它加入字典中且距离为1且要加入到path,Line 10。
- 建图的邻接表,对没有边的节点也要加到邻接表,所以先对所有点赋空列表,再根据边更新值,Line 29。用defaultdict(list)可解决
- DFS模板中去掉visited部分,因为用了最短距离distance的map来指导访问路径,所以不会存在循环的情况(否则不会是最短距离)
而且如果有visited会存在丢解,因为如果一个节点不在最短路径上先被访问就会被标记为visited,真正到最短路径上时就会返回。
DFS模板中加入if dict[neighbor] == dict[startWord] + 1来剪边。
Python代码:
1 | def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[int]]: |
Java代码:
1 | public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) { |
算法分析:
getNextWords是L26L=O(L2)
产生新字符串需要L
时间复杂度为O(nL2 + mk)
,空间复杂度O(n)
,m为答案个数, k为最短路径值,n为单词数。