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"]
]
Analysis:
BFS. store all shortest path to each node. Wheneven, generate a neighbor node from current node, determine whether it is in dict and in queue. If in queue, then determine whether the path from src to current node then to it has the same length with the already generated path of this neighbor node, if yes, then add all the new paths from src to current node to neighbor into the path set of the neighbor node.
Solution:
1 public class Solution { 2 public List<List<String>> findLadders(String start, String end, Set<String> dict) { 3 List<List<String>> res = new ArrayList<List<String>>(); 4 List<String> nodeList = new ArrayList<String>(); 5 List<Integer> levelList = new ArrayList<Integer>(); 6 Map<String,List<List<String>>> resSet = new HashMap<String,List<List<String>>>(); 7 8 nodeList.add(start); 9 levelList.add(1); 10 List<List<String>> nodeRes = new ArrayList<List<String>>(); 11 List<String> onePath = new ArrayList<String>(); 12 onePath.add(start); 13 nodeRes.add(onePath); 14 resSet.put(start,nodeRes); 15 16 int cur = 0; 17 boolean findEnd = false; 18 while (cur<nodeList.size()){ 19 int curLevel = levelList.get(cur); 20 while (cur<nodeList.size() && levelList.get(cur)==curLevel){ 21 String curNode = nodeList.get(cur); 22 nodeRes = resSet.get(curNode); 23 for (int i=0;i<curNode.length();i++) 24 for (int j=0;j<26;j++){ 25 char[] temp = curNode.toCharArray(); 26 temp[i] = (char) ('a'+j); 27 String newNode = new String(temp); 28 if (dict.contains(newNode) && !resSet.containsKey(newNode)){ 29 nodeList.add(newNode); 30 levelList.add(curLevel+1); 31 List<List<String>> newRes = new ArrayList<List<String>>(); 32 for (int k=0;k<nodeRes.size();k++){ 33 onePath = new ArrayList<String>(); 34 onePath.addAll(nodeRes.get(k)); 35 onePath.add(newNode); 36 newRes.add(onePath); 37 } 38 resSet.put(newNode,newRes); 39 } else if (dict.contains(newNode) && resSet.containsKey(newNode) && nodeRes.get(0).size()+1<=resSet.get(newNode).get(0).size()){ 40 List<List<String>> newRes = resSet.get(newNode); 41 for (int k=0;k<nodeRes.size();k++){ 42 onePath = new ArrayList<String>(); 43 onePath.addAll(nodeRes.get(k)); 44 onePath.add(newNode); 45 newRes.add(onePath); 46 } 47 } 48 49 if (newNode.equals(end)){ 50 findEnd = true; 51 } 52 } 53 cur++; 54 } 55 if (findEnd) break; 56 } 57 58 if (!findEnd) 59 return (new ArrayList<List<String>>()); 60 else return resSet.get(end); 61 } 62 }