题目：
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.
链接： https//leetcode.com/problems/word-ladder-ii/
题解：
求所有最短路径...第一想法是先定义一个用adjacent list表示的图类，然后用Dijkstra求最短路径们。
再仔细想一想，我们现在应该有两条路，一条是在Word Ladder I的基础上改进， 另外一条是用一个不太一样的方法从头思考设计和解决。
先试试第一条，在Word Ladder I基础上改进。一个可能的解法基本步骤可能是:
- 按照Word Ladder I的方法，用BFS求最段路径
- 找到第一条最短路径的时候，不返回，继续计算Queue里这一层BFS其他结点，看是否能有其他最短路径。 因为在这一层找到了最短路径，所以长度是固定的，找完这一层就可以结束了，返回结果。
- 在每一层BFS的时候cache之前路径。对于 visited的处理，在每一层运算结束之后再统一更新visited，否则如果下一节点由这一层的多个节点共用，会出问题。
- 如何保存已经访问过的节点。比如假设用 HashMap<String, List<String>>来保存下一节点与之前路径，假设有一条为 tex, {red，ted，tex}，还有一条 tex，{red，rex，tex}，这时就有了collision。所以可能只能储存前序的节点，并不能保存整个路径，除非额外做些处理，比如另外做数据结构，或者把路径做成 word + delimiter，然后比较的时候取split string得到的数组里的最后一个元素， 之类的。
- 只存前序节点的话，最后的结果应该是在HashMap里的一条<endWord, List<String>>。 这样再从endWord开始对List<String>做一个DFS，应该就可以找到所要求的路径。
12:53AM，尝试完毕，可以作为一个解。要继续研究最优解法。终于AC了好高兴，基本算是做了整整一天。写的代码丑陋异常...一定要再优化优化。复杂度应该和1一样，不过代码里面用到了list的contains，也许会增加一些低阶量。
Time Complexity - O(min(26^L, size(wordList))， Space Complexity - O(min(26^L, size(wordList))， L为 word length。
public class Solution {
public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) {
List<List<String>> res = new ArrayList<>();
if(beginWord == null || endWord == null || wordList == null || wordList.size() == 0 || beginWord.equals(endWord))
return res;
if(wordList.contains(beginWord))
wordList.remove(beginWord);
if(wordList.contains(endWord))
wordList.remove(endWord);
Queue<String> q = new LinkedList<>();
q.offer(beginWord);
int curLevel = 1, nextLevel = 0;
HashSet<String> visited = new HashSet<>();
HashSet<String> levelVisited = new HashSet<>();
HashMap<String, ArrayList<String>> wordChains = new HashMap<>();
boolean foundShortestPath = false;
while(!q.isEmpty()) {
String word = q.poll();
curLevel--;
for(int i = 0; i < word.length(); i++) {
char[] wordAsArray = word.toCharArray();
for(char j = 'a'; j <= 'z'; j++) {
wordAsArray[i] = j;
String newWord = String.valueOf(wordAsArray);
if(newWord.equals(endWord)) { // found shortest path at this level
foundShortestPath = true; // flag to only process this level, then return
if(wordChains.containsKey(endWord)) {
if(!wordChains.get(endWord).contains(word))
wordChains.get(endWord).add(word);
} else {
ArrayList<String> preWords = new ArrayList<>();
preWords.add(word);
wordChains.put(endWord, preWords);
}
break;
}
if(wordList.contains(newWord) && !visited.contains(newWord)) { //found edge to next node
q.offer(newWord);
if(wordChains.containsKey(newWord)) {
if(!wordChains.get(newWord).contains(word))
wordChains.get(newWord).add(word);
} else {
ArrayList<String> preWords = new ArrayList<>();
preWords.add(word);
wordChains.put(newWord, preWords);
}
nextLevel++;
levelVisited.add(newWord); //add the newWord to a temp visited HashMap
}
}
}
if(curLevel == 0) {
if(foundShortestPath)
break;
curLevel = nextLevel;
nextLevel = 0;
for(String str : levelVisited) //update the global "visited"
visited.add(str);
levelVisited.clear();
}
}
ArrayList<String> list = new ArrayList<>();
list.add(endWord);
getWordChains(res, list, wordChains, beginWord, endWord);
return res;
}
private void getWordChains(List<List<String>> res, ArrayList<String> list, HashMap<String, ArrayList<String>> wordChains, String beginWord, String endWord) {
if(endWord.equals(beginWord)) {
res.add(new ArrayList<String>(list));
return;
}
ArrayList<String> curLevel= new ArrayList<>();
if(wordChains.containsKey(endWord))
curLevel = wordChains.get(endWord);
else
return;
for(int i = 0; i < curLevel.size(); i++) {
String word = curLevel.get(i);
list.add(0, word);
getWordChains(res, list, wordChains, beginWord, word);
list.remove(word);
}
}
}
再试试第二条(刷下一遍时)
急需学习图的各种知识。WordLadder这种经典题目，Sedgewick的算法书和Mark Ellen Weiss的数据结构书里都有涉及，要多学多练。
题外话： 中午去SOHO和Justin谈了一下，他说有3个startup不错，一个是doubleclick前CEO做的，专门搞古董交易的startup。第二个是ADP sponsor的internal子公司，做得很像zenefits。第三个是一个做男士剃须刀的，有专门的厂家在德国，目标是在你需要刮胡子的时候快递新的刮胡刀上门。真的很有意思，broaden my vision。 下午继续回公司做事，要处理好和同事，上级的关系，要有耐心，不要急躁。
Reference：
http://baike.baidu.com/view/349189.htm
https://zh.wikipedia.org/wiki/%E6%9C%80%E7%9F%AD%E8%B7%AF%E9%97%AE%E9%A2%98
http://blog.csdn.net/v_july_v/article/details/6181485
http://www.geeksforgeeks.org/breadth-first-traversal-for-a-graph/
http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/Graph.java.html
http://www.cnblogs.com/springfor/p/3893529.html
http://blog.csdn.net/linhuanmars/article/details/23071455