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 intermediate word must exist in the word list
For example,

Given:

``````beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
``````

Return

``````[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
``````

Note:

• All words have the same length.
• All words contain only lowercase alphabetic characters.

## Solution

BFS + DFS

II的解法也有很多种，但是却不容易[AC]通过，主要原因是时间复杂度太大： 造成时间复杂度过大的可能有两个原因：

(题外话：我称这种为小学生思路，因为我觉得如果让一个小学生来做这类题目，他们可能往往想到的就是这种最朴素的解决办法。而由于大部分程序员的思路会受到刷题训练的限制，往往想到iteration就是用while或者for loop来遍历，而忽略了看似简单幼稚，实则可能更实用的解法)

(1) 在原因1.解决的前提下，既然用BFS去寻找第一条最短路径是肯定不会超时的，那么如果我用一个时间复杂度不大于BFS的算法去找出所有路径，也不会超时；

(2) 我先想到了DFS，但是还不知道如何应用DFS去解决。我先在纸上画出了BFS的队列模型，试着找出线索。

``````start = hit
end = cog
dict = [hot,dot,dog,lot,log,dof,mit,sit,set,mog,mig,seg,nax,max]
Return
[["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"],
["hit","mit","mig","mog","cog"]]
``````

``````level 1: [hit]
level 2: [mit, sit, hot]
level 3: [mig, set, dot, lot]
level 4: [mog, seg, dof, dog, log]
level 5: [cog]
``````

(1) 字典中其他尚未遍历到的单词，比如naxmax，如何处理，是否可以被忽略？ 必要性

(2) BFS建立的层级结构，它包含了所有可能构成最短路径的word吗？ 充分性

## Code

``````public class Solution {
public List<List<String>> findLadders(String start, String end, Set<String> dict) {
List<List<String>> res = new ArrayList<List<String>>();
if(start.compareTo(end) == 0) return res;
Set<String> visited = new HashSet<String>();
Set<String> cur = new HashSet<String>();
HashMap<String, ArrayList<String>> graph = new HashMap<String, ArrayList<String>>();
graph.put(end,new ArrayList<String>());
boolean found = false;
while (cur.isEmpty() == false && found == false) {
Set<String> queue = new HashSet<String>();
for(Iterator<String> it=cur.iterator();it.hasNext();) {
}
for(Iterator<String> it=cur.iterator();it.hasNext();) {
String str = it.next();
char[] word = str.toCharArray();
for (int j = 0; j < word.length; ++j) {
char before = word[j];
for (char ch = 'a'; ch <= 'z'; ++ch) {
if (ch == before) continue;
word[j] = ch;
String temp = new String(word);
if (dict.contains(temp) == false) continue;
if (found == true && end.compareTo(temp) != 0) continue;
if (end.compareTo(temp) == 0) {
found = true;
continue;
}
if (visited.contains(temp) == false) {
if (graph.containsKey(temp) == false) {
ArrayList<String> l = new ArrayList<String>();
graph.put(temp,l);
} else {
}
}
}
word[j] = before;
}
}
cur = queue;
}
if (found == true) {
ArrayList<String> path = new ArrayList<String>();
trace(res, graph, path, start, end);
}
return res;
}
public void trace(List<List<String>> res,
HashMap<String, ArrayList<String>> graph,
ArrayList<String> path,
String start, String now) {
if (now.compareTo(start) == 0) {
ArrayList<String> ans = new ArrayList<String>(path);
Collections.reverse(ans);