Word Ladder II
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 timeEach intermediate word must exist in the dictionaryFor example,Given:start = "hit"end = "cog"dict = ["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 1:
这题做得真累，主页君差点一口老血吐在屏幕上，感觉一不小心就会超时了。
其实最后还是可以采用跟Word Ladder 1一样的解法。使用BFS遍历可能的解。不同的有以下几点：
1. 分层次遍历的时候，不要把找到的解的单词直接放在MAP中，而是可以放在别的一个临时的MAP中，一层遍历完成后，再统一加到MAP。这样做的上的是：
如果本层找到一个单词比如Word，本层的其它单词如果也可以到达Word，我们仍然要把它的解都记下来。
2. 添加到队列的时候，也要判断是不是一个新的单词（在临时MAP中查一下），是新的才能放在Queue中，否则因为1的关系，我们会计算某个单词的所有的解，所以会一直访问它。为了避免重复加入一个单词，这一步是有必要的。
3. 与Word Ladder1中的set不同，我们使用一个hasmap来记录路径中的单词，另外，每一个单词对应的value是一个string的list,记录到达此单词的所有的可能的路径。创建这些路径的方法是：把前节点的所有的路径加上当前单词，复制一份加过来即可。
REF:
1 public class Solution { 2 public static List > findLadders(String start, String end, Set dict) { 3 if (start == null || end == null) { 4 return null; 5 } 6 7 Queue q = new LinkedList (); 8 9 // 存储每一个单词对应的路径10 HashMap >> map = new HashMap >>();11 12 // 标记在某一层找到解13 boolean find = false;14 15 // store the length of the start string.16 int lenStr = start.length();17 18 List > list = new ArrayList >();19 20 // 唯一的路径21 List path = new ArrayList ();22 path.add(start);23 list.add(path);24 25 // 将头节点放入26 map.put(start, list);27 q.offer(start);28 29 while (!q.isEmpty()) {30 int size = q.size();31 32 HashMap >> mapTmp = new HashMap >>(); 33 for (int i = 0; i < size; i++) {34 // get the current word.35 String str = q.poll();36 for (int j = 0; j < lenStr; j++) {37 StringBuilder sb = new StringBuilder(str);38 for (char c = 'a'; c <= 'z'; c++) {39 sb.setCharAt(j, c);40 String tmp = sb.toString();41 42 // 1. 重复的单词，不需要计算。因为之前一层出现过，再出现只会更长43 // 2. 必须要在字典中出现44 if (map.containsKey(tmp) || (!dict.contains(tmp) && !tmp.equals(end))) {45 continue;46 }47 48 // 将前节点的路径提取出来49 List > pre = map.get(str);50 51 // 从mapTmp中取出节点，或者是新建一个节点52 List > curList = mapTmp.get(tmp);53 if (curList == null) {54 // Create a new list and add to the end word.55 curList = new ArrayList >();56 mapTmp.put(tmp, curList);57 58 // 将生成的单词放入队列，以便下一次继续变换59 // 放在这里可以避免Q重复加入60 q.offer(tmp);61 }62 63 // 将PRE的path 取出，加上当前节点，并放入curList中64 for(List pathPre: pre) {65 List pathNew = new ArrayList (pathPre);66 pathNew.add(tmp);67 curList.add(pathNew);68 }69 70 if (tmp.equals(end)) {71 find = true;72 }73 }74 }75 }76 77 if (find) {78 return mapTmp.get(end);79 }80 81 // 把当前层找到的解放在MAP中。82 // 使用2个map的原因是：在当前层中，我们需要把同一个单词的所有的解全部找出来.83 map.putAll(mapTmp);84 }85 86 // 返回一个空的结果87 return new ArrayList >();88 }89 }
2014.12.18 Redo:
做了一个小小的优化，拿掉了Find Flag:
1 public class Solution { 2 public static List > findLadders(String start, String end, Set dict) { 3 List > ret = new ArrayList >(); 4 if (start == null || end == null || dict == null) { 5 return ret; 6 } 7 8 HashMap >> map = new HashMap >>(); 9 10 // Store the map of the current level.11 HashMap >> mapTmp = new HashMap >>();12 13 Queue q = new LinkedList ();14 q.offer(start);15 16 List > listStart = new ArrayList >();17 18 // 唯一的路径19 List path = new ArrayList ();20 path.add(start);21 listStart.add(path);22 23 // 将头节点放入24 map.put(start, listStart);25 26 while (!q.isEmpty()) {27 int size = q.size();28 29 for (int i = 0; i < size; i++) {30 String s = q.poll();31 32 int len = s.length();33 for (int j = 0; j < len; j++) {34 StringBuilder sb = new StringBuilder(s);35 for (char c = 'a'; c <= 'z'; c++) {36 // Bug 2: should seperate the setCharAt(j, c) function and the sb.toString() function.37 sb.setCharAt(j, c);38 String tmp = sb.toString();39 40 // 1. 不在字典中，并且不是end.41 // 2. 前面的map中已经出现过42 43 // Bug 1: map should use containsKey;44 if ((!dict.contains(tmp) && !tmp.equals(end)) || map.containsKey(tmp)) {45 continue;46 }47 48 // Try to get the pre list.49 List > pre = map.get(s);50 51 // 从mapTmp中取出节点，或者是新建一个节点52 List > curList = mapTmp.get(tmp);53 if (curList == null) {54 curList = new ArrayList >();55 56 // Only offer new string to the queue.57 // 将生成的单词放入队列，以便下一次继续变换58 // 放在这里可以避免Q重复加入59 q.offer(tmp);60 61 // create a new map.62 mapTmp.put(tmp, curList);63 }64 65 // 将PRE的path 取出，加上当前节点，并放入curList中66 for (List strList: pre) {67 // Should create a new list. 68 List strListNew = new ArrayList (strList);69 strListNew.add(tmp);70 curList.add(strListNew);71 }72 }73 }74 }75 76 if (mapTmp.containsKey(end)) {77 return mapTmp.get(end);78 }79 80 // add the tmp map into the map.81 map.putAll(mapTmp);82 }83 84 return ret;85 }86 }
SOLUTION 2:
GITHUB: