Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:
Only one letter can be changed at a time
Each intermediate word must exist in the dictionary
For example,
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
Return
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
解题思路：
本题应该是目前遇到的最Hard的一道了，思路先按照Java for LeetCode 127 Word Ladder的代码进行dfs找到 ladderLength 然后以 ladderLength 为步长进行DFS，这里进行DFS需要从后往前（因为disMap是从前往后建立的，从前往后的话前期肯定有无数匹配，从后往前的话，只要匹配就是要找到alist）
JAVA实现如下：
static public List<List<String>> findLadders(String start, String end,Set<String> dict) {
List<List<String>> result = new LinkedList<List<String>>();
LinkedList<String> queue = new LinkedList<String>();
HashMap<String, Integer> disMap = new HashMap<String, Integer>();
queue.add(start);
disMap.put(start, 1);
int depth = -1;
findDepth: while (!queue.isEmpty()) {
String word = queue.poll();
for (int i = 0; i < word.length(); i++) {
StringBuilder sb = new StringBuilder(word);
for (char ch = 'a'; ch <= 'z'; ch++) {
sb.setCharAt(i, ch);
String nextWord = sb.toString();
if (nextWord.equals(end)) {
depth = disMap.get(word) + 1;
break findDepth;
}
if (dict.contains(nextWord)
&& !disMap.containsKey(nextWord)) {
queue.add(nextWord);
disMap.put(nextWord, disMap.get(word) + 1);
}
}
}
}
if (depth > 0)
dfs(result, start, end, disMap, depth,new LinkedList<String>());
return result;
}
static void dfs(List<List<String>> result, String start, String end,HashMap<String, Integer> disMap, int depth,List<String> alist) {
alist.add(0, end);
if (end.equals(start))
result.add(new LinkedList<String>(alist));
if (depth <= 1)
return;
String word = alist.get(0);
for (int i = 0; i < word.length(); i++) {
StringBuilder sb = new StringBuilder(word);
for (char ch = 'a'; ch <= 'z'; ch++) {
sb.setCharAt(i, ch);
String nextWord = sb.toString();
if (disMap.containsKey(nextWord)&&disMap.get(nextWord)==depth-1) {
dfs(result, start, nextWord, disMap, depth - 1,alist);
alist.remove(0);
}
}
}
}