题目：
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"] ]
Note:
- All words have the same length.
- All words contain only lowercase alphabetic characters.
题解：
答案是http://www.1point3acres.com/bbs/thread-51646-1-1.html 上面 写的。
我就直接贴过来就好，这道题多读读代码看明白。
代码：
1 public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) { 2 3 HashMap<String, HashSet<String>> neighbours = new HashMap<String, HashSet<String>>(); 4 5 dict.add(start); 6 dict.add(end); 7 8 // init adjacent graph 9 for(String str : dict){ 10 calcNeighbours(neighbours, str, dict); 11 } 12 13 ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>(); 14 15 // BFS search queue 16 LinkedList<Node> queue = new LinkedList<Node>(); 17 queue.add( new Node( null, start, 1)); // the root has not parent and its level == 1 18 19 // BFS level 20 int previousLevel = 0; 21 22 // mark which nodes have been visited, to break infinite loop 23 HashMap<String, Integer> visited = new HashMap<String, Integer>(); 24 while(!queue.isEmpty()){ 25 Node n = queue.pollFirst(); 26 if(end.equals(n.str)){ 27 // fine one path, check its length, if longer than previous path it's valid 28 // otherwise all possible short path have been found, should stop 29 if(previousLevel == 0 || n.level == previousLevel){ 30 previousLevel = n.level; 31 findPath(n, result); 32 } else { 33 // all path with length *previousLevel* have been found 34 break; 35 } 36 } else { 37 HashSet<String> set = neighbours.get(n.str); 38 39 if(set == null || set.isEmpty()) continue; 40 // note: I'm not using simple for(String s: set) here. This is to avoid hashset's 41 // current modification exception. 42 ArrayList<String> toRemove = new ArrayList<String>(); 43 for (String s : set) { 44 45 // if s has been visited before at a smaller level, there is already a shorter 46 // path from start to s thus we should ignore s so as to break infinite loop; if 47 // on the same level, we still need to put it into queue. 48 if(visited.containsKey(s)){ 49 Integer occurLevel = visited.get(s); 50 if(n.level+1 > occurLevel){ 51 neighbours.get(s).remove(n.str); 52 toRemove.add(s); 53 continue; 54 } 55 } 56 visited.put(s, n.level+1); 57 queue.add( new Node(n, s, n.level + 1)); 58 if(neighbours.containsKey(s)) 59 neighbours.get(s).remove(n.str); 60 } 61 for(String s: toRemove){ 62 set.remove(s); 63 } 64 } 65 } 66 67 return result; 68 } 69 70 public void findPath(Node n, ArrayList<ArrayList<String>> result){ 71 ArrayList<String> path = new ArrayList<String>(); 72 Node p = n; 73 while(p != null){ 74 path.add(0, p.str); 75 p = p.parent; 76 } 77 result.add(path); 78 } 79 80 /* 81 * complexity: O(26*str.length*dict.size)=O(L*N) 82 */ 83 void calcNeighbours(HashMap<String, HashSet<String>> neighbours, String str, HashSet<String> dict) { 84 int length = str.length(); 85 char [] chars = str.toCharArray(); 86 for ( int i = 0; i < length; i++) { 87 88 char old = chars[i]; 89 for ( char c = 'a'; c <= 'z'; c++) { 90 91 if (c == old) continue; 92 chars[i] = c; 93 String newstr = new String(chars); 94 95 if (dict.contains(newstr)) { 96 HashSet<String> set = neighbours.get(str); 97 if (set != null) { 98 set.add(newstr); 99 } else { 100 HashSet<String> newset = new HashSet<String>(); 101 newset.add(newstr); 102 neighbours.put(str, newset); 103 } 104 } 105 } 106 chars[i] = old; 107 } 108 } 109 110 private class Node { 111 public Node parent; // previous node 112 public String str; 113 public int level; 114 public Node(Node p, String s, int l){ 115 parent = p; 116 str = s; 117 level = l; 118 } 119 }
Reference：http://www.1point3acres.com/bbs/thread-51646-1-1.html