Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:
Only one letter can be changed at a time
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:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
Output: []
Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.
Note
这个题还是挺难的，一开始看的时候完全没有头绪，需要用到bfs和dfs的知识
本题需要我们找到最短路径的所有结果，我们可以把每个单词当作一个node，构建图。node的neighbor是于其只差一个字母并且在wordList中的其他字符串。bfs构建图，如果遇到endWord，此时的level 最深。
举个栗子
Eg.
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
level0 hit
level1 hot
level2 dot lot 这里注意，不要把hit也包含在hot的neighbors 里面了
level3 dog log
level4 cog
neighbors:
hit : [hot]
hot: [dot, lot]
dot:[dog]
lot:[log]
dot:[cog]
log:[cog]
我们可以track level防止bfs像之前的levels搜索, 最后通过dfs找出所有的结果。 minLevel 用来剪纸，如果我们找到end，把当前level赋值给minLevel, 由于bfs找到的第一个end的路径最小（可以思考下为什么），如果当前level > minLevel 直接不去遍历。
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
Set<String> dict = new HashSet<>(wordList);
List<List<String>> res = new ArrayList<>();
Map<String, Integer> level = new HashMap<>();
for (String s : dict) {
level.put(s, Integer.MAX_VALUE);
}
level.put(beginWord, 0);
Map<String, List<String>> neighbors = new HashMap<>();
Queue<String> queue = new LinkedList<>();
queue.offer(beginWord);
int minLevel = Integer.MAX_VALUE;
while (!queue.isEmpty()) {
String cur = queue.poll();
int nextStep = level.get(cur) + 1;
if (nextStep > minLevel) break;
for (int i = 0; i < cur.length(); i++) {
char[] chars = cur.toCharArray();
for (char c = 'a'; c <= 'z'; c++) {
chars[i] = c;
String newWord = String.valueOf(chars);
if (dict.contains(newWord)) {
if (nextStep > level.get(newWord)) {
continue;
} else if (nextStep < level.get(newWord)){
level.put(newWord, nextStep);
queue.offer(newWord);
}
if (neighbors.containsKey(cur)) {
neighbors.get(cur).add(newWord);
} else {
List<String> l = new ArrayList<>();
l.add(newWord);
neighbors.put(cur, l);
}
}
if (newWord.equals(endWord)) {
minLevel = nextStep;
}
}
}
}
List<String> solution = new ArrayList<>();
dfs(beginWord, endWord, res, solution, neighbors);
return res;
}
private void dfs(String cur, String end, List<List<String>> res, List<String> solution, Map<String, List<String>> neighbors ) {
solution.add(cur);
if (cur.equals(end)) {
res.add(new ArrayList<>(solution));
} else {
List<String> myNeighbors = neighbors.get(cur);
if (myNeighbors != null) {
for (String n : myNeighbors) {
dfs(n, end, res,solution, neighbors);
}
}
}
solution.remove(solution.size() - 1);
}
