Related: LeetCode:Word Ladder I
LeetCode:Word Ladder I II - tenos - 博客园
Still looking for better/cleaner solution
Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:
http://eugeneyang.com/2016/02/15/Word%20Ladder%20II%20-%20%E8%AF%8D%E6%A2%AFII/
http://blog.csdn.net/niaokedaoren/article/details/8884938
http://www.programcreek.com/2014/06/leetcode-word-ladder-ii-java/
http://blog.csdn.net/muscler/article/details/22906533
X. two-end BFS
https://discuss.leetcode.com/topic/17975/super-fast-java-solution-two-end-bfs
X. BFS then DFS
https://discuss.leetcode.com/topic/27504/my-concise-java-solution-based-on-bfs-and-dfs
http://www.guoting.org/leetcode/leetcode-126-word-ladder-ii/
https://leetcode.com/discuss/294/java-implementation-vs-c-implementation
When searching in BFS, maintain parent pointer of each node discovered in current level back to parent node in previous level, and finally use DFS to find all path from end to start.
public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) { //<String, Queue> contaion all the adjacent words that is discover in its previous level HashMap<String, Queue<String>> adjMap = new HashMap<String, Queue<String>>(); int currLen = 0; boolean found = false; ArrayList<ArrayList<String>> r = new ArrayList<ArrayList<String>>();//results Queue<String> queue = new LinkedList<String>(); //queue for BFS Set<String> unVisited = new HashSet<String>(dict); //unvisited words Set<String> visitedThisLev = new HashSet<String>(); //check words visited during same level unVisited.add(end); queue.offer(start); int currLev = 1; int nextLev = 0; for(String word : unVisited){ adjMap.put(word, new LinkedList<String>()); } unVisited.remove(start); //BFS while( !queue.isEmpty() ){ String currLadder = queue.poll(); //for all unvisited words that are one character change from current word for(String nextLadder : getNextLadder(currLadder, unVisited)){ if(visitedThisLev.add(nextLadder)) { nextLev ++; queue.offer(nextLadder); } adjMap.get(nextLadder).offer(currLadder); if(nextLadder.equals(end) && !found) { found = true; currLen+=2;} } if(--currLev == 0){ if(found) break; unVisited.removeAll(visitedThisLev); currLev = nextLev; nextLev = 0; currLen ++; } } if(found){ LinkedList<String> p =new LinkedList<String>(); p.addFirst(end); getLadders(start, end, p , r, adjMap, currLen); } return r; } //get all unvisited words that are one character change from current word private ArrayList<String> getNextLadder(String currLadder, Set<String> unVisited){ ArrayList<String> nextLadders = new ArrayList<String>(); StringBuffer replace = new StringBuffer(currLadder); for(int i = 0; i < currLadder.length(); i++){ char old = replace.charAt(i); for(char ch = 'a'; ch <= 'z'; ch++){ replace.setCharAt(i, ch); String replaced = replace.toString(); if(ch != currLadder.charAt(i) && unVisited.contains(replaced) ){ nextLadders.add(replaced); } } replace.setCharAt(i, old); } return nextLadders; } // DFS to get all possible path from start to end private void getLadders(String start, String currLadder, LinkedList<String> p, ArrayList<ArrayList<String>> solu, HashMap<String, Queue<String>> adjMap, int len){ if(currLadder.equals(start)){ solu.add(new ArrayList<String> (p)); } else if(len > 0) { Queue<String> adjs = adjMap.get(currLadder); for(String lad : adjs){ p.addFirst(lad); getLadders(start, lad, p, solu, adjMap, len-1); p.removeFirst(); } } }
https://leetcode.com/discuss/64808/my-concise-java-solution-based-on-bfs-and-dfs
public List<List<String>> findLadders(String start, String end, Set<String> dict) {
List<List<String>> res = new ArrayList<List<String>>();
HashMap<String, ArrayList<String>> nodeNeighbors = new HashMap<String, ArrayList<String>>();// Neighbors for every node
HashMap<String, Integer> distance = new HashMap<String, Integer>();// Distance of every node from the start node
ArrayList<String> solution = new ArrayList<String>();
dict.add(end);
bfs(start, end, dict, nodeNeighbors, distance);
// check whether there is solution first dfs(start, end, dict, nodeNeighbors, distance, solution, res); return res; } // BFS: Trace every node's distance from the start node (level by level). private void bfs(String start, String end, Set<String> dict, HashMap<String, ArrayList<String>> nodeNeighbors, HashMap<String, Integer> distance) { for (String str : dict) nodeNeighbors.put(str, new ArrayList<String>());//not needed Queue<String> queue = new LinkedList<String>(); queue.offer(start); distance.put(start, 0); while (!queue.isEmpty()) { int count = queue.size(); boolean foundEnd = false; for (int i = 0; i < count; i++) { String cur = queue.poll(); int curDistance = distance.get(cur); ArrayList<String> neighbors = getNeighbors(cur, dict); for (String neighbor : neighbors) { nodeNeighbors.get(cur).add(neighbor); if (!distance.containsKey(neighbor)) {// Check if visited distance.put(neighbor, curDistance + 1); if (end.equals(neighbor))// Found the shortest path foundEnd = true; else queue.offer(neighbor); } } } if (foundEnd) break; } } // Find all next level nodes. private ArrayList<String> getNeighbors(String node, Set<String> dict) { ArrayList<String> res = new ArrayList<String>(); char chs[] = node.toCharArray(); for (char ch ='a'; ch <= 'z'; ch++) { for (int i = 0; i < chs.length; i++) { if (chs[i] == ch) continue; char old_ch = chs[i]; chs[i] = ch; if (dict.contains(String.valueOf(chs))) { res.add(String.valueOf(chs)); } chs[i] = old_ch; } } return res; } // DFS: output all paths with the shortest distance. private void dfs(String cur, String end, Set<String> dict, HashMap<String, ArrayList<String>> nodeNeighbors, HashMap<String, Integer> distance, ArrayList<String> solution, List<List<String>> res) { solution.add(cur); if (end.equals(cur)) { res.add(new ArrayList<String>(solution)); } else { for (String next : nodeNeighbors.get(cur)) { if (distance.get(next) == distance.get(cur) + 1) { dfs(next, end, dict, nodeNeighbors, distance, solution, res); } } } solution.remove(solution.size() - 1); }
http://www.jiuzhang.com/solutions/word-ladder-ii/
http://huangyawu.com/leetcode-word-ladder-ii-java/
http://siyang2leetcode.blogspot.com/2015/01/word-ladder-ii.html
本题可以分两步求解，第一步使用BFS求解出所有的最短的字梯解集合，然后在解集合中使用DFS搜索问题的解
X.
https://leetcode.com/discuss/294/java-implementation-vs-c-implementation
X. Two-End BFS
https://leetcode.com/discuss/44110/super-fast-java-solution-two-end-bfs
public List<List<String>> findLadders(String start, String end, Set<String> dict) { // hash set for both ends Set<String> set1 = new HashSet<String>(); Set<String> set2 = new HashSet<String>(); // initial words in both ends set1.add(start); set2.add(end); // we use a map to help construct the final result Map<String, List<String>> map = new HashMap<String, List<String>>(); // build the map helper(dict, set1, set2, map, false); List<List<String>> res = new ArrayList<List<String>>(); List<String> sol = new ArrayList<String>(Arrays.asList(start)); // recursively build the final result generateList(start, end, map, sol, res); return res; } boolean helper(Set<String> dict, Set<String> set1, Set<String> set2, Map<String, List<String>> map, boolean flip) { if (set1.isEmpty()) { return false; } if (set1.size() > set2.size()) { return helper(dict, set2, set1, map, !flip); } // remove words on current both ends from the dict dict.removeAll(set1); dict.removeAll(set2); // as we only need the shortest paths // we use a boolean value help early termination boolean done = false; // set for the next level Set<String> set = new HashSet<String>(); // for each string in end 1 for (String str : set1) { for (int i = 0; i < str.length(); i++) { char[] chars = str.toCharArray(); // change one character for every position for (char ch = 'a'; ch <= 'z'; ch++) { chars[i] = ch; String word = new String(chars); // make sure we construct the tree in the correct direction String key = flip ? word : str; String val = flip ? str : word; List<String> list = map.containsKey(key) ? map.get(key) : new ArrayList<String>(); if (set2.contains(word)) { done = true; list.add(val); map.put(key, list); } if (!done && dict.contains(word)) { set.add(word); list.add(val); map.put(key, list); } } } } // early terminate if done is true return done || helper(dict, set2, set, map, !flip); } void generateList(String start, String end, Map<String, List<String>> map, List<String> sol, List<List<String>> res) { if (start.equals(end)) { res.add(new ArrayList<String>(sol)); return; } // need this check in case the diff between start and end happens to be one // e.g "a", "c", {"a", "b", "c"} if (!map.containsKey(start)) { return; } for (String word : map.get(start)) { sol.add(word); generateList(word, end, map, sol, res); sol.remove(sol.size() - 1); } }
http://www.zrzahid.com/the-word-navigation-game/
We can use a queue to perform BFS.
public class BFSData {
public Queue<PathNode> toVisit = new LinkedList<PathNode>();
public HashMap<String, PathNode> visited = new HashMap<String, PathNode>();
public BFSData(String root) {
PathNode sourcePath = new PathNode(root, null);
toVisit.add(sourcePath);
visited.put(root, sourcePath);
}
public boolean isFinished() {
return toVisit.isEmpty();
}
}
public class PathNode {
private String word = null;
private PathNode previousNode = null;
public PathNode(String word, PathNode previous) {
this.word = word;
previousNode = previous;
}
public String getWord() {
return word;
}
/* Traverse path and return linked list of nodes. */
public LinkedList<String> collapse(boolean startsWithRoot) {
LinkedList<String> path = new LinkedList<String>();
PathNode node = this;
while (node != null) {
if (startsWithRoot) {
path.addLast(node.word);
} else {
path.addFirst(node.word);
}
node = node.previousNode;
}
return path;
}
}
public static LinkedList<String> transform(String startWord, String stopWord, String[] words) {
HashMapList<String, String> wildcardToWordList = getWildcardToWordList(words);
BFSData sourceData = new BFSData(startWord);
BFSData destData = new BFSData(stopWord);
while (!sourceData.isFinished() && !destData.isFinished()) {
/* Search out from source. */
String collision = searchLevel(wildcardToWordList, sourceData, destData);
if (collision != null) {
return mergePaths(sourceData, destData, collision);
}
/* Search out from destination. */
collision = searchLevel(wildcardToWordList, destData, sourceData);
if (collision != null) {
return mergePaths(sourceData, destData, collision);
}
}
return null;
}
/* Search one level and return collision, if any. */
public static String searchLevel(HashMapList<String, String> wildcardToWordList, BFSData primary, BFSData secondary) {
/* We only want to search one level at a time. Count how many nodes are currently in the primary's
* level and only do that many nodes. We'll continue to add nodes to the end. */
int count = primary.toVisit.size();
for (int i = 0; i < count; i++) {
/* Pull out first node. */
PathNode pathNode = primary.toVisit.poll();
String word = pathNode.getWord();
/* Check if it's already been visited. */
if (secondary.visited.containsKey(word)) {
return pathNode.getWord();
}
/* Add friends to queue. */
ArrayList<String> words = getValidLinkedWords(word, wildcardToWordList);
for (String w : words) {
if (!primary.visited.containsKey(w)) {
PathNode next = new PathNode(w, pathNode);
primary.visited.put(w, next);
primary.toVisit.add(next);
}
}
}
return null;
}
public static LinkedList<String> mergePaths(BFSData bfs1, BFSData bfs2, String connection) {
PathNode end1 = bfs1.visited.get(connection); // end1 -> source
PathNode end2 = bfs2.visited.get(connection); // end2 -> dest
LinkedList<String> pathOne = end1.collapse(false); // forward: source -> connection
LinkedList<String> pathTwo = end2.collapse(true); // reverse: connection -> dest
pathTwo.removeFirst(); // remove connection
pathOne.addAll(pathTwo); // add second path
return pathOne;
}
public static LinkedList<String> transform(String start, String stop, String[] words) {
HashMapList<String, String> wildcardToWordList = createWildcardToWordMap(words);
HashSet<String> visited = new HashSet<String>();
return transform(visited, start, stop, wildcardToWordList);
}
/* Do a depth-first search from start to stop, traveling through each word that is one edit away. */
public static LinkedList<String> transform(HashSet<String> visited, String start, String stop, HashMapList<String, String> wildcardToWordList) {
if (start.equals(stop)) {
LinkedList<String> path = new LinkedList<String>();
path.add(start);
return path;
} else if (visited.contains(start)) {
return null;
}
visited.add(start);
ArrayList<String> words = getValidLinkedWords(start, wildcardToWordList);
for (String word : words) {
LinkedList<String> path = transform(visited, word, stop, wildcardToWordList);
if (path != null) {
path.addFirst(start);
return path;
}
}
return null;
}
/* Insert words in dictionary into mapping from wildcard form -> word. */
public static HashMapList<String, String> createWildcardToWordMap(String[] words) {
HashMapList<String, String> wildcardToWords = new HashMapList<String, String>();
for (String word : words) {
ArrayList<String> linked = getWildcardRoots(word);
for (String linkedWord : linked) {
wildcardToWords.put(linkedWord, word);
}
}
return wildcardToWords;
}
/* Get list of wildcards associated with word. */
public static ArrayList<String> getWildcardRoots(String w) {
ArrayList<String> words = new ArrayList<String>();
for (int i = 0; i < w.length(); i++) {
String word = w.substring(0, i) + "_" + w.substring(i + 1);
words.add(word);
}
return words;
}
/* Return words that are one edit away. */
public static ArrayList<String> getValidLinkedWords(String word, HashMapList<String, String> wildcardToWords) {
ArrayList<String> wildcards = getWildcardRoots(word);
ArrayList<String> linkedWords = new ArrayList<String>();
for (String wildcard : wildcards) {
ArrayList<String> words = wildcardToWords.get(wildcard);
for (String linkedWord : words) {
if (!linkedWord.equals(word)) {
linkedWords.add(linkedWord);
}
}
}
return linkedWords;
}
public static ArrayList<String> wordsOneAway(String word) {
ArrayList<String> words = new ArrayList<String>();
for (int i = 0; i < word.length(); i++) {
for (char c = 'a'; c <= 'z'; c++) {
String w = word.substring(0, i) + c + word.substring(i + 1);
words.add(w);
}
}
return words;
}
public static LinkedList<String> transform(HashSet<String> visited, String startWord, String stopWord, Set<String> dictionary) {
if (startWord.equals(stopWord)) {
LinkedList<String> path = new LinkedList<String>();
path.add(startWord);
return path;
} else if (visited.contains(startWord) || !dictionary.contains(startWord)) {
return null;
}
visited.add(startWord);
ArrayList<String> words = wordsOneAway(startWord);
for (String word : words) {
LinkedList<String> path = transform(visited, word, stopWord, dictionary);
if (path != null) {
path.addFirst(startWord);
return path;
}
}
return null;
}
public static LinkedList<String> transform(String start, String stop, String[] words) {
HashSet<String> dict = setupDictionary(words);
HashSet<String> visited = new HashSet<String>();
return transform(visited, start, stop, dict);
}
public static HashSet<String> setupDictionary(String[] words) {
HashSet<String> hash = new HashSet<String>();
for (String word : words) {
hash.add(word.toLowerCase());
}
return hash;
}
https://scyforce.gitbooks.io/leetcode/content/word_ladder_ii.html
https://discuss.leetcode.com/topic/7387/java-solution-with-iteration
TODO: http://siyang2leetcode.blogspot.com/2015/01/word-ladder-ii.html
https://discuss.leetcode.com/topic/9156/java-modified-bfs-to-find-end-followed-by-dfs-to-reconstruct-paths
Read full article from LeetCode:Word Ladder I II - tenos - 博客园
LeetCode:Word Ladder I II - tenos - 博客园
Still looking for better/cleaner solution
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
The solution contains two steps 1 Use BFS to construct a graph. 2. Use DFS to construct the paths from end to start.Both solutions got AC within 1s.
The first step BFS is quite important. I summarized three tricks
- Using a MAP to store the min ladder of each word, or use a SET to store the words visited in current ladder, when the current ladder was completed, delete the visited words from unvisited. That's why I have two similar solutions.
- Use Character iteration to find all possible paths. Do not compare one word to all the other words and check if they only differ by one character.
- One word is allowed to be inserted into the queue only ONCE
Map<String,List<String>> map;
List<List<String>> results;
public List<List<String>> findLadders(String start, String end, Set<String> dict) {
results= new ArrayList<List<String>>();
if (dict.size() == 0)
return results;
int min=Integer.MAX_VALUE;
Queue<String> queue= new ArrayDeque<String>();
queue.add(start);
map = new HashMap<String,List<String>>();
Map<String,Integer> ladder = new HashMap<String,Integer>();
for (String string:dict)
ladder.put(string, Integer.MAX_VALUE);
ladder.put(start, 0);
dict.add(end);
//BFS: Dijisktra search
while (!queue.isEmpty()) {
String word = queue.poll();
int step = ladder.get(word)+1;//'step' indicates how many steps are needed to travel to one word.
if (step>min) break;
for (int i = 0; i < word.length(); i++){
StringBuilder builder = new StringBuilder(word);
for (char ch='a'; ch <= 'z'; ch++){
builder.setCharAt(i,ch);
String new_word=builder.toString();
if (ladder.containsKey(new_word)) {
if (step>ladder.get(new_word))//Check if it is the shortest path to one word.
continue;
else if (step<ladder.get(new_word)){
queue.add(new_word);
ladder.put(new_word, step);
}else;// It is a KEY line. If one word already appeared in one ladder,
// Do not insert the same word inside the queue twice. Otherwise it gets TLE.
if (map.containsKey(new_word)) //Build adjacent Graph
map.get(new_word).add(word);
else{
List<String> list= new LinkedList<String>();
list.add(word);
map.put(new_word,list);
//It is possible to write three lines in one:
//map.put(new_word,new LinkedList<String>(Arrays.asList(new String[]{word})));
//Which one is better?
}
if (new_word.equals(end))
min=step;
}//End if dict contains new_word
}//End:Iteration from 'a' to 'z'
}//End:Iteration from the first to the last
}//End While
//BackTracking
LinkedList<String> result = new LinkedList<String>(); // using char[]
backTrace(end,start,result);
return results;
}
private void backTrace(String word,String start,List<String> list){
if (word.equals(start)){
list.add(0,start); // add, remove is slow
results.add(new ArrayList<String>(list));
list.remove(0);
return;
}
list.add(0,word);
if (map.get(word)!=null)
for (String s:map.get(word))
backTrace(s,start,list);
list.remove(0);
}
一、 怎样保证求得所有的最短路径；二、 怎样构造这些路径
第一问题：
- 不能像上一题第二点注意那样，找到一个单词相邻的单词后就立马把它从字典里删除，因为当前层还有其他单词可能和该单词是相邻的，这也是一条最短路径，比如hot->hog->dog->dig和hot->dot->dog->dig，找到hog的相邻dog后不能立马删除，因为和hog同一层的单词dot的相邻也是dog，两者均是一条最短路径。但是为了避免进入死循环，再hog、dot这一层的单词便利完成后dog还是得从字典中删除。即等到当前层所有单词遍历完后，和他们相邻且在字典中的单词要从字典中删除。
- 如果像上面那样没有立马删除相邻单词，就有可能把同一个单词加入bfs队列中，这样就会有很多的重复计算（比如上面例子提到的dog就会被2次加入队列）。因此我们用一个哈希表来保证加入队列中的单词不会重复，哈希表在每一层遍历完清空（代码中hashtable）。
- 当某一层的某个单词转换可以得到end单词时，表示已经找到一条最短路径，那么该单词的其他转换就可以跳过。并且遍历完这一层以后就可以跳出循环，因为再往下遍历，肯定会超过最短路径长度
第二个问题：
- 为了输出最短路径，我们就要在比bfs的过程中保存好前驱节点，比如单词hog通过一次变换可以得到hot，那么hot的前驱节点就包含hog，每个单词的前驱节点有可能不止一个，那么每个单词就需要一个数组来保存前驱节点。为了快速查找因此我们使用哈希表来保存所有单词的前驱路径，哈希表的key是单词，value是单词数组。（代码中的unordered_map<string,vector<string> >prePath）
- 有了上面的前驱路径，可以从目标单词开始递归的构造所有最短路径（代码中的函数 ConstructResult）
http://eugeneyang.com/2016/02/15/Word%20Ladder%20II%20-%20%E8%AF%8D%E6%A2%AFII/
注意：将chars字符数组转换成String千万别写成了chars.toString(); ，不小心犯了这个低级错误会很麻烦。
http://www.cnblogs.com/shawnhue/archive/2013/06/05/leetcode_126.htmlhttp://blog.csdn.net/niaokedaoren/article/details/8884938
只能把每个单词所对应的前驱单词记录下来，当然有可能有多个，那么
就用一个vector<string>存储好，有这些记录就可以重构路径了。
前一个解决方案虽然能通过大数据集测试，但是为了保存路径信息我们额外引入了一个结构体而且因为需要用到指针使用了大量的new操作。还有什么不用保存所有路径信息的办法？
niaokedaoren的方案中使用了一个前驱单词表，即记录每一个单词的前驱单词是哪些。这样在遍历完毕后，我们从end出发递归就能把所有路径生成出来。但是由于前驱单词表不能记录当前的层次信息，似乎我们没法完成去重的工作。这个方案的巧妙之处就在于它没有使用我们通常的队列保存待处理的单词，一个单词一个单词先进先出处理的方法，而是使用两个vector来模拟队列的操作。我们从vector 1中遍历单词进行转换尝试，发现能转换的单词后将其放入vector 2中。当vector 1中的单词处理完毕后即为一层处理完毕，它里面的单词就可以从字典里删去了。接着我们对vector 2进行同样处理，如此反复直到当前处理的vector中不再有单词。我们发现vector 1和vector 2在不断地交换正处理容器和待处理容器的身份，因此可以通过将其放入一个数组中，每次循环对数组下标值取反实现身份的交替：
http://huangyawu.com/leetcode-word-ladder-ii-java/http://www.programcreek.com/2014/06/leetcode-word-ladder-ii-java/
The idea is the same. To track the actual ladder, we need to add a pointer that points to the previous node in the WordNode class.
In addition, the used word can not directly removed from the dictionary. The used word is only removed when steps change.
class WordNode{ String word; int numSteps; WordNode pre; public WordNode(String word, int numSteps, WordNode pre){ this.word = word; this.numSteps = numSteps; this.pre = pre; } } |
public List<List<String>> findLadders(String start, String end, Set<String> dict) { List<List<String>> result = new ArrayList<List<String>>(); LinkedList<WordNode> queue = new LinkedList<WordNode>(); queue.add(new WordNode(start, 1, null)); dict.add(end); int minStep = 0; HashSet<String> visited = new HashSet<String>(); HashSet<String> unvisited = new HashSet<String>(); unvisited.addAll(dict); int preNumSteps = 0; while(!queue.isEmpty()){ WordNode top = queue.remove(); String word = top.word; int currNumSteps = top.numSteps; if(word.equals(end)){ if(minStep == 0){ minStep = top.numSteps; } if(top.numSteps == minStep && minStep !=0){ //nothing ArrayList<String> t = new ArrayList<String>(); t.add(top.word); while(top.pre !=null){ t.add(0, top.pre.word); top = top.pre; } result.add(t); continue; } } if(preNumSteps < currNumSteps){ unvisited.removeAll(visited); } preNumSteps = currNumSteps; char[] arr = word.toCharArray(); for(int i=0; i<arr.length; i++){ for(char c='a'; c<='z'; c++){ char temp = arr[i]; if(arr[i]!=c){ arr[i]=c; } String newWord = new String(arr); if(unvisited.contains(newWord)){ queue.add(new WordNode(newWord, top.numSteps+1, top)); visited.add(newWord); } arr[i]=temp; } } } return result; }
http://blog.csdn.net/muscler/article/details/22906533
X. two-end BFS
https://discuss.leetcode.com/topic/17975/super-fast-java-solution-two-end-bfs
I have two further improvements in return:
- There is no needs for helper method to return boolean. It is useless and can be more concise.
- List<String> list = map.containsKey(key) ? map.get(key) : new ArrayList<String>(); should be in the if block in order to save memory. Two if blocks can be merged into one block actually.
public List<List<String>> findLadders(String start, String end, Set<String> dict) {
// hash set for both ends
Set<String> set1 = new HashSet<String>();
Set<String> set2 = new HashSet<String>();
// initial words in both ends
set1.add(start);
set2.add(end);
// we use a map to help construct the final result
Map<String, List<String>> map = new HashMap<String, List<String>>();
// build the map
helper(dict, set1, set2, map, false);
List<List<String>> res = new ArrayList<List<String>>();
List<String> sol = new ArrayList<String>(Arrays.asList(start));
// recursively build the final result
generateList(start, end, map, sol, res);
return res;
}
boolean helper(Set<String> dict, Set<String> set1, Set<String> set2, Map<String, List<String>> map, boolean flip) {
if (set1.isEmpty()) {
return false;
}
if (set1.size() > set2.size()) {
return helper(dict, set2, set1, map, !flip);
}
// remove words on current both ends from the dict
dict.removeAll(set1);
dict.removeAll(set2);
// as we only need the shortest paths
// we use a boolean value help early termination
boolean done = false;
// set for the next level
Set<String> set = new HashSet<String>();
// for each string in end 1
for (String str : set1) {
for (int i = 0; i < str.length(); i++) {
char[] chars = str.toCharArray();
// change one character for every position
for (char ch = 'a'; ch <= 'z'; ch++) {
chars[i] = ch;
String word = new String(chars);
// make sure we construct the tree in the correct direction
String key = flip ? word : str;
String val = flip ? str : word;
List<String> list = map.containsKey(key) ? map.get(key) : new ArrayList<String>();
if (set2.contains(word)) {
done = true;
list.add(val);
map.put(key, list);
}
if (!done && dict.contains(word)) {
set.add(word);
list.add(val);
map.put(key, list);
}
}
}
}
// early terminate if done is true
return done || helper(dict, set2, set, map, !flip);
}
void generateList(String start, String end, Map<String, List<String>> map, List<String> sol, List<List<String>> res) {
if (start.equals(end)) {
res.add(new ArrayList<String>(sol));
return;
}
// need this check in case the diff between start and end happens to be one
// e.g "a", "c", {"a", "b", "c"}
if (!map.containsKey(start)) {
return;
}
for (String word : map.get(start)) {
sol.add(word);
generateList(word, end, map, sol, res);
sol.remove(sol.size() - 1);
}
}X. BFS then DFS
https://discuss.leetcode.com/topic/27504/my-concise-java-solution-based-on-bfs-and-dfs
http://www.guoting.org/leetcode/leetcode-126-word-ladder-ii/
The basic idea is:
1). Use BFS to find the shortest distance between start and end, tracing the distance of crossing nodes from start node to end node, and store node's next level neighbors to HashMap;
2). Use DFS to output paths with the same distance as the shortest distance from distance HashMap: compare if the distance of the next level node equals the distance of the current node + 1.
public List<List<String>> findLadders(String start, String end, Set<String> dict) {
List<List<String>> res = new ArrayList<List<String>>();
HashMap<String, ArrayList<String>> nodeNeighbors = new HashMap<String, ArrayList<String>>();// Neighbors for every node
HashMap<String, Integer> distance = new HashMap<String, Integer>();// Distance of every node from the start node
ArrayList<String> solution = new ArrayList<String>();
dict.add(end);
bfs(start, end, dict, nodeNeighbors, distance);
dfs(start, end, dict, nodeNeighbors, distance, solution, res);
return res;
}
// BFS: Trace every node's distance from the start node (level by level).
private void bfs(String start, String end, Set<String> dict, HashMap<String, ArrayList<String>> nodeNeighbors, HashMap<String, Integer> distance) {
for (String str : dict)
nodeNeighbors.put(str, new ArrayList<String>());
Queue<String> queue = new LinkedList<String>();
queue.offer(start);
distance.put(start, 0);
while (!queue.isEmpty()) {
int count = queue.size();
boolean foundEnd = false;
for (int i = 0; i < count; i++) {
String cur = queue.poll();
int curDistance = distance.get(cur);
ArrayList<String> neighbors = getNeighbors(cur, dict);
for (String neighbor : neighbors) {
nodeNeighbors.get(cur).add(neighbor);
if (!distance.containsKey(neighbor)) {// Check if visited
distance.put(neighbor, curDistance + 1);
if (end.equals(neighbor))// Found the shortest path
foundEnd = true;
else
queue.offer(neighbor);
}
}
}
if (foundEnd)
break;
}
}
// Find all next level nodes.
private ArrayList<String> getNeighbors(String node, Set<String> dict) {
ArrayList<String> res = new ArrayList<String>();
char chs[] = node.toCharArray();
for (char ch ='a'; ch <= 'z'; ch++) {
for (int i = 0; i < chs.length; i++) {
if (chs[i] == ch) continue;
char old_ch = chs[i];
chs[i] = ch;
if (dict.contains(String.valueOf(chs))) {
res.add(String.valueOf(chs));
}
chs[i] = old_ch;
}
}
return res;
}
// DFS: output all paths with the shortest distance.
private void dfs(String cur, String end, Set<String> dict, HashMap<String, ArrayList<String>> nodeNeighbors, HashMap<String, Integer> distance, ArrayList<String> solution, List<List<String>> res) {
solution.add(cur);
if (end.equals(cur)) {
res.add(new ArrayList<String>(solution));
}
else {
for (String next : nodeNeighbors.get(cur)) {
if (distance.get(next) == distance.get(cur) + 1) {
dfs(next, end, dict, nodeNeighbors, distance, solution, res);
}
}
}
solution.remove(solution.size() - 1);
}
The solution contains two steps 1 Use BFS to construct a graph. 2. Use DFS to construct the paths from end to start.Both solutions got AC within 1s.
The first step BFS is quite important. I summarized three tricks
- Using a MAP to store the min ladder of each word, or use a SET to store the words visited in current ladder, when the current ladder was completed, delete the visited words from unvisited. That's why I have two similar solutions.
- Use Character iteration to find all possible paths. Do not compare one word to all the other words and check if they only differ by one character.
- One word is allowed to be inserted into the queue only ONCE. See my comments.
Map<String,List<String>> map;
List<List<String>> results;
public List<List<String>> findLadders(String start, String end, Set<String> dict) {
results= new ArrayList<List<String>>();
if (dict.size() == 0)
return results;
int min=Integer.MAX_VALUE;
Queue<String> queue= new ArrayDeque<String>();
queue.add(start);
map = new HashMap<String,List<String>>();
Map<String,Integer> ladder = new HashMap<String,Integer>();
for (String string:dict)
ladder.put(string, Integer.MAX_VALUE);
ladder.put(start, 0);
dict.add(end);
//BFS: Dijisktra search
while (!queue.isEmpty()) {
String word = queue.poll();
int step = ladder.get(word)+1;//'step' indicates how many steps are needed to travel to one word.
if (step>min) break;
for (int i = 0; i < word.length(); i++){
StringBuilder builder = new StringBuilder(word);
for (char ch='a'; ch <= 'z'; ch++){
builder.setCharAt(i,ch);
String new_word=builder.toString();
if (ladder.containsKey(new_word)) {
if (step>ladder.get(new_word))//Check if it is the shortest path to one word.
continue;
else if (step<ladder.get(new_word)){
queue.add(new_word);
ladder.put(new_word, step);
}else;// It is a KEY line. If one word already appeared in one ladder,
// Do not insert the same word inside the queue twice. Otherwise it gets TLE.
if (map.containsKey(new_word)) //Build adjacent Graph
map.get(new_word).add(word);
else{
List<String> list= new LinkedList<String>();
list.add(word);
map.put(new_word,list);
//It is possible to write three lines in one:
//map.put(new_word,new LinkedList<String>(Arrays.asList(new String[]{word})));
//Which one is better?
}
if (new_word.equals(end))
min=step;
}//End if dict contains new_word
}//End:Iteration from 'a' to 'z'
}//End:Iteration from the first to the last
}//End While
//BackTracking
LinkedList<String> result = new LinkedList<String>();
backTrace(end,start,result);
return results;
}
private void backTrace(String word,String start,List<String> list){
if (word.equals(start)){
list.add(0,start);
results.add(new ArrayList<String>(list));
list.remove(0);
return;
}
list.add(0,word);
if (map.get(word)!=null)
for (String s:map.get(word))
backTrace(s,start,list);
list.remove(0);
}
}
Another solution using two sets. This is similar to the answer in the most viewed thread. While I found my solution more readable and efficient.
List<List<String>> results;
List<String> list;
Map<String,List<String>> map;
public List<List<String>> findLadders(String start, String end, Set<String> dict) {
results= new ArrayList<List<String>>();
if (dict.size() == 0)
return results;
int curr=1,next=0;
boolean found=false;
list = new LinkedList<String>();
map = new HashMap<String,List<String>>();
Queue<String> queue= new ArrayDeque<String>();
Set<String> unvisited = new HashSet<String>(dict);
Set<String> visited = new HashSet<String>();
queue.add(start);
unvisited.add(end);
unvisited.remove(start);
//BFS
while (!queue.isEmpty()) {
String word = queue.poll();
curr--;
for (int i = 0; i < word.length(); i++){
StringBuilder builder = new StringBuilder(word);
for (char ch='a'; ch <= 'z'; ch++){
builder.setCharAt(i,ch);
String new_word=builder.toString();
if (unvisited.contains(new_word)){
//Handle queue
if (visited.add(new_word)){//Key statement,Avoid Duplicate queue insertion
next++;
queue.add(new_word);
}
if (map.containsKey(new_word))//Build Adjacent Graph
map.get(new_word).add(word);
else{
List<String> l= new LinkedList<String>();
l.add(word);
map.put(new_word, l);
}
if (new_word.equals(end)&&!found) found=true;
}
}//End:Iteration from 'a' to 'z'
}//End:Iteration from the first to the last
if (curr==0){
if (found) break;
curr=next;
next=0;
unvisited.removeAll(visited);
visited.clear();
}
}//End While
backTrace(end,start);
return results;
}
private void backTrace(String word,String start){
if (word.equals(start)){
list.add(0,start);
results.add(new ArrayList<String>(list));
list.remove(0);
return;
}
list.add(0,word);
if (map.get(word)!=null)
for (String s:map.get(word))
backTrace(s,start);
list.remove(0);
}
}https://leetcode.com/discuss/294/java-implementation-vs-c-implementation
When searching in BFS, maintain parent pointer of each node discovered in current level back to parent node in previous level, and finally use DFS to find all path from end to start.
public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) { //<String, Queue> contaion all the adjacent words that is discover in its previous level HashMap<String, Queue<String>> adjMap = new HashMap<String, Queue<String>>(); int currLen = 0; boolean found = false; ArrayList<ArrayList<String>> r = new ArrayList<ArrayList<String>>();//results Queue<String> queue = new LinkedList<String>(); //queue for BFS Set<String> unVisited = new HashSet<String>(dict); //unvisited words Set<String> visitedThisLev = new HashSet<String>(); //check words visited during same level unVisited.add(end); queue.offer(start); int currLev = 1; int nextLev = 0; for(String word : unVisited){ adjMap.put(word, new LinkedList<String>()); } unVisited.remove(start); //BFS while( !queue.isEmpty() ){ String currLadder = queue.poll(); //for all unvisited words that are one character change from current word for(String nextLadder : getNextLadder(currLadder, unVisited)){ if(visitedThisLev.add(nextLadder)) { nextLev ++; queue.offer(nextLadder); } adjMap.get(nextLadder).offer(currLadder); if(nextLadder.equals(end) && !found) { found = true; currLen+=2;} } if(--currLev == 0){ if(found) break; unVisited.removeAll(visitedThisLev); currLev = nextLev; nextLev = 0; currLen ++; } } if(found){ LinkedList<String> p =new LinkedList<String>(); p.addFirst(end); getLadders(start, end, p , r, adjMap, currLen); } return r; } //get all unvisited words that are one character change from current word private ArrayList<String> getNextLadder(String currLadder, Set<String> unVisited){ ArrayList<String> nextLadders = new ArrayList<String>(); StringBuffer replace = new StringBuffer(currLadder); for(int i = 0; i < currLadder.length(); i++){ char old = replace.charAt(i); for(char ch = 'a'; ch <= 'z'; ch++){ replace.setCharAt(i, ch); String replaced = replace.toString(); if(ch != currLadder.charAt(i) && unVisited.contains(replaced) ){ nextLadders.add(replaced); } } replace.setCharAt(i, old); } return nextLadders; } // DFS to get all possible path from start to end private void getLadders(String start, String currLadder, LinkedList<String> p, ArrayList<ArrayList<String>> solu, HashMap<String, Queue<String>> adjMap, int len){ if(currLadder.equals(start)){ solu.add(new ArrayList<String> (p)); } else if(len > 0) { Queue<String> adjs = adjMap.get(currLadder); for(String lad : adjs){ p.addFirst(lad); getLadders(start, lad, p, solu, adjMap, len-1); p.removeFirst(); } } }
https://leetcode.com/discuss/64808/my-concise-java-solution-based-on-bfs-and-dfs
1). Use BFS to find the shortest distance between start and end, tracing the distance of crossing nodes from start node to end node, and store node's next level neighbors to HashMap;
2). Use DFS to output paths with the same distance as the shortest distance from distance HashMap: compare if the distance of the next level node equals the distance of the current node + 1.
if (foundEnd)
break;
Why should we break here? Now maybe not all nodes in this level (which is 'count') have been examined, right? We only know this cur's neighbor is endWord, while maybe next 'cur' in the same level still has endWord as its neighbor so we got another path! Why should we jump out of the level here?
// check whether there is solution first dfs(start, end, dict, nodeNeighbors, distance, solution, res); return res; } // BFS: Trace every node's distance from the start node (level by level). private void bfs(String start, String end, Set<String> dict, HashMap<String, ArrayList<String>> nodeNeighbors, HashMap<String, Integer> distance) { for (String str : dict) nodeNeighbors.put(str, new ArrayList<String>());//not needed Queue<String> queue = new LinkedList<String>(); queue.offer(start); distance.put(start, 0); while (!queue.isEmpty()) { int count = queue.size(); boolean foundEnd = false; for (int i = 0; i < count; i++) { String cur = queue.poll(); int curDistance = distance.get(cur); ArrayList<String> neighbors = getNeighbors(cur, dict); for (String neighbor : neighbors) { nodeNeighbors.get(cur).add(neighbor); if (!distance.containsKey(neighbor)) {// Check if visited distance.put(neighbor, curDistance + 1); if (end.equals(neighbor))// Found the shortest path foundEnd = true; else queue.offer(neighbor); } } } if (foundEnd) break; } } // Find all next level nodes. private ArrayList<String> getNeighbors(String node, Set<String> dict) { ArrayList<String> res = new ArrayList<String>(); char chs[] = node.toCharArray(); for (char ch ='a'; ch <= 'z'; ch++) { for (int i = 0; i < chs.length; i++) { if (chs[i] == ch) continue; char old_ch = chs[i]; chs[i] = ch; if (dict.contains(String.valueOf(chs))) { res.add(String.valueOf(chs)); } chs[i] = old_ch; } } return res; } // DFS: output all paths with the shortest distance. private void dfs(String cur, String end, Set<String> dict, HashMap<String, ArrayList<String>> nodeNeighbors, HashMap<String, Integer> distance, ArrayList<String> solution, List<List<String>> res) { solution.add(cur); if (end.equals(cur)) { res.add(new ArrayList<String>(solution)); } else { for (String next : nodeNeighbors.get(cur)) { if (distance.get(next) == distance.get(cur) + 1) { dfs(next, end, dict, nodeNeighbors, distance, solution, res); } } } solution.remove(solution.size() - 1); }
http://www.jiuzhang.com/solutions/word-ladder-ii/
public List<List<String>> findLadders(String start, String end, Set<String> dict) { List<List<String>> ladders = new ArrayList<List<String>>(); Map<String, List<String>> map = new HashMap<String, List<String>>(); Map<String, Integer> distance = new HashMap<String, Integer>(); dict.add(start); dict.add(end); bfs(map, distance, start, end, dict); List<String> path = new ArrayList<String>(); dfs(ladders, path, end, start, distance, map); return ladders; } void dfs(List<List<String>> ladders, List<String> path, String crt, String start, Map<String, Integer> distance, Map<String, List<String>> map) { path.add(crt); if (crt.equals(start)) { Collections.reverse(path); ladders.add(new ArrayList<String>(path)); Collections.reverse(path); } else { for (String next : map.get(crt)) { if (distance.containsKey(next) && distance.get(crt) == distance.get(next) + 1) { dfs(ladders, path, next, start, distance, map); } } } path.remove(path.size() - 1); } void bfs(Map<String, List<String>> map, Map<String, Integer> distance, String start, String end, Set<String> dict) { Queue<String> q = new LinkedList<String>(); q.offer(start); distance.put(start, 0); for (String s : dict) { map.put(s, new ArrayList<String>()); } while (!q.isEmpty()) { String crt = q.poll(); List<String> nextList = expand(crt, dict); for (String next : nextList) { map.get(next).add(crt); if (!distance.containsKey(next)) { distance.put(next, distance.get(crt) + 1); q.offer(next); } } } } List<String> expand(String crt, Set<String> dict) { List<String> expansion = new ArrayList<String>(); for (int i = 0; i < crt.length(); i++) { for (char ch = 'a'; ch <= 'z'; ch++) { if (ch != crt.charAt(i)) { String expanded = crt.substring(0, i) + ch + crt.substring(i + 1); if (dict.contains(expanded)) { expansion.add(expanded); } } } } return expansion; }
http://huangyawu.com/leetcode-word-ladder-ii-java/
http://siyang2leetcode.blogspot.com/2015/01/word-ladder-ii.html
本题可以分两步求解，第一步使用BFS求解出所有的最短的字梯解集合，然后在解集合中使用DFS搜索问题的解
public class Solution { private HashMap<String, Integer> map; private void dfs(String word, String end, List<String> sequence, List<List<String>> res){ if(map.get(word) == map.get(end) && !end.equals(word)) return; else if(end.equals(word)){ List<String> list = new LinkedList<String>(sequence); list.add(word); Collections.reverse(list); res.add(list); return; } sequence.add(word); for(int i=0; i<word.length(); i++){ char[] wordArray = word.toCharArray(); for(char ch = 'a'; ch <= 'z'; ch++){ if(wordArray[i] == ch) continue; wordArray[i] = ch; String tmp = new String(wordArray); if(map.containsKey(tmp) && map.get(tmp) == (map.get(word) - 1)) dfs(tmp, end, sequence, res); } } sequence.remove(word); } public List<List<String>> findLadders(String start, String end, Set<String> dict) { List<List<String>> res = new ArrayList<List<String>>(); LinkedList<String> queue = new LinkedList<String>(); map = new HashMap<String, Integer>(); queue.add(start); map.put(start, 1); if(start.equals(end)){ res.add(queue); return res; } while(!queue.isEmpty()){ String word = queue.poll(); for(int i=0; i<word.length(); i++){ char[] wordArray = word.toCharArray(); for(char j='a'; j<='z'; j++){ if(wordArray[i] == j) continue; wordArray[i] = j; String tmp = new String(wordArray); if(tmp.endsWith(end)){ map.put(tmp, map.get(word)+1); i = word.length(); queue.clear(); break; } if(dict.contains(tmp) && !map.containsKey(tmp)){ map.put(tmp, map.get(word) + 1); queue.add(tmp); } } } } if(map.containsKey(end)) dfs(end, start, new LinkedList<String>(), res); return res; }}X.
https://leetcode.com/discuss/294/java-implementation-vs-c-implementation
BFS but with little trick - represent paths as string, so don't need backward traverse, when reach the end (have all path at once):
* hithotdot
* hit --> hithot -->
* hithotlot
*/
public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) {
int n = start.length();
Set<String> chains = new HashSet<>();
chains.add(start);
Map<String, Boolean> repeat = new HashMap<>();
repeat.put(start, true);
boolean[] stop = new boolean[1];
while(!stop[0]) {
chains = getOneEditWords(chains, dict, repeat, stop, n, end);
for(String chain : chains) {
repeat.put(chain.substring(chain.length() - n), true);
}
}
ArrayList<ArrayList<String>> res = new ArrayList<>();
for(String chain : chains) {
if(chain.endsWith(end)) {
ArrayList<String> r = new ArrayList<>();
for(int i = 0; i <= chain.length() - n; i = i + n) {
r.add(chain.substring(i, i + n));
}
res.add(r);
}
}
return res;
}
Set<String> getOneEditWords(Set<String> chains, HashSet<String> dict, Map<String, Boolean> repeat, boolean[] stop, int n, String end) {
Map<String, Set<String>> cache = new HashMap<>();
Set<String> res = new HashSet<>();
for(String chain : chains) {
String lastWord = chain.substring(chain.length() - n);
Set<String> generated = new HashSet<>();
if(cache.containsKey(lastWord)) {
generated = cache.get(lastWord);
}
else {
for(int i = 0; i < lastWord.length(); i++) {
char[] wordArray = lastWord.toCharArray();
for(char c = 'a'; c <= 'z'; c++) {
if(c != lastWord.charAt(i)) {
wordArray[i] = c;
String gen = new String(wordArray);
if(gen.equals(end)) {
stop[0] = true;
}
if(dict.contains(gen) && !repeat.containsKey(gen)) {
generated.add(gen);
}
}
}
}
cache.put(lastWord, generated);
}
for(String s : generated) {
res.add(chain + s);
}
}
if (res.isEmpty()){
stop[0] = true;
}
return res;
}X. Two-End BFS
https://leetcode.com/discuss/44110/super-fast-java-solution-two-end-bfs
public List<List<String>> findLadders(String start, String end, Set<String> dict) { // hash set for both ends Set<String> set1 = new HashSet<String>(); Set<String> set2 = new HashSet<String>(); // initial words in both ends set1.add(start); set2.add(end); // we use a map to help construct the final result Map<String, List<String>> map = new HashMap<String, List<String>>(); // build the map helper(dict, set1, set2, map, false); List<List<String>> res = new ArrayList<List<String>>(); List<String> sol = new ArrayList<String>(Arrays.asList(start)); // recursively build the final result generateList(start, end, map, sol, res); return res; } boolean helper(Set<String> dict, Set<String> set1, Set<String> set2, Map<String, List<String>> map, boolean flip) { if (set1.isEmpty()) { return false; } if (set1.size() > set2.size()) { return helper(dict, set2, set1, map, !flip); } // remove words on current both ends from the dict dict.removeAll(set1); dict.removeAll(set2); // as we only need the shortest paths // we use a boolean value help early termination boolean done = false; // set for the next level Set<String> set = new HashSet<String>(); // for each string in end 1 for (String str : set1) { for (int i = 0; i < str.length(); i++) { char[] chars = str.toCharArray(); // change one character for every position for (char ch = 'a'; ch <= 'z'; ch++) { chars[i] = ch; String word = new String(chars); // make sure we construct the tree in the correct direction String key = flip ? word : str; String val = flip ? str : word; List<String> list = map.containsKey(key) ? map.get(key) : new ArrayList<String>(); if (set2.contains(word)) { done = true; list.add(val); map.put(key, list); } if (!done && dict.contains(word)) { set.add(word); list.add(val); map.put(key, list); } } } } // early terminate if done is true return done || helper(dict, set2, set, map, !flip); } void generateList(String start, String end, Map<String, List<String>> map, List<String> sol, List<List<String>> res) { if (start.equals(end)) { res.add(new ArrayList<String>(sol)); return; } // need this check in case the diff between start and end happens to be one // e.g "a", "c", {"a", "b", "c"} if (!map.containsKey(start)) { return; } for (String word : map.get(start)) { sol.add(word); generateList(word, end, map, sol, res); sol.remove(sol.size() - 1); } }
http://www.zrzahid.com/the-word-navigation-game/
We can use a queue to perform BFS.
public static boolean isNavigable(final String src, final String dst, final Set<String> dictionary) { if (src.length() != dst.length()) { return false; } if (src.equals(dst)) { return true; } dictionary.remove(src); final LinkedList<String> q = new LinkedList<String>(); q.add(src); while (!q.isEmpty()) { final String intermediate = q.remove(); for (int i = 0; i < intermediate.length(); i++) { char[] candidateChars = intermediate.toCharArray(); for (char j = 'A'; j < 'Z'; j++) { candidateChars[i] = j; final String candidate = new String(candidateChars); if (candidate.equals(dst)) { System.out.print("-->" + candidate); return true; } else if (dictionary.contains(candidate)) { dictionary.remove(candidate); q.add(candidate); System.out.print("-->" + candidate); } } } } return false; }
How to find all possible shortest transformations?
while we are traversing in BFS we can maintain the total numbers of transformations. We can use this as the length of a path from the source word. If current transformation (i.e. a candidate word that presents in dictionary) was previously generated by some other intermediate word then we have two choice – either take this path if it leads to a shorter path to solution then the previous path or don’t take current path and discard this transformation. We can easily do this using Dijkstra’s shortest path invariant where we only update a neighbor path len when pathLen[mine]+1 <= pathLen[neighbor]. Also, we each time we select a transformed candidate word to visit , we will update its parent to the the intermediate word it is transformed from so that later we can reconstruct the path.public static List<List<String>> wordLadderAll(Set<String> dictionary, String src, String dst){ if(src == null || dst == null || dictionary == null || src.isEmpty() || dst.isEmpty() || dictionary.isEmpty()){ return Collections.EMPTY_LIST; } //Queue to traverse in BFS Queue<String> queue = new ArrayDeque<String>(); //path from a node to its parent along the BFS traversal Map<String, String> parent = new HashMap<String, String>(); //level of a word appeared in the DAG Map<String, Integer> pathLen = new HashMap<String, Integer>(); //min length path so far int minLen = Integer.MAX_VALUE; //resulting shortest paths List<List<String>> paths = new ArrayList<>(); //resulting shortest path last nodes Set<String> shortestPathLeaves = new HashSet<String>(); //add source to queue to start traversing queue.add(src); pathLen.put(src, 0); while(!queue.isEmpty()){ String intermediate = queue.poll(); //we already have a shortest path, so discard this longer path if(pathLen.get(intermediate) >= minLen){ continue; } //BFS to each possible 1 edit distance neighbors in dictionary for(int i = 0; i<intermediate.length(); i++){ char[] candidateChars = intermediate.toCharArray(); //all possible words with current character variations for(char c = 'a'; c < 'z'; c++){ candidateChars[i] = c; String candidate = new String(candidateChars); if(!pathLen.containsKey(candidate)){ pathLen.put(candidate, Integer.MAX_VALUE); } //Dijktra's shortest path formullae if(pathLen.get(intermediate)+1 > pathLen.get(candidate)){ continue; } //if we reach a solution, add it to solution if(candidate.equals(dst)){ shortestPathLeaves.add(intermediate); minLen = Math.min(minLen, pathLen.get(intermediate)+1); } //otherwise if this intermediate word is present in dictionary then //add it as children and update the path len else if(dictionary.contains(candidate)){ parent.put(candidate, intermediate); pathLen.put(candidate, pathLen.get(intermediate)+1); queue.add(candidate); } } } } //Add all paths to result set for(String path : shortestPathLeaves){ paths.add(getPath(parent, path, src, dst)); } return paths; } private static List<String> getPath(Map<String, String> parentMap, String leaf, String src, String dst){ List<String> path = new ArrayList<String>(); String node = leaf; path.add(dst); path.add(0, leaf); while(parentMap.get(node) != null && parentMap.get(node) != src){ node = parentMap.get(node); path.add(0, node); } path.add(0, src); return path; }https://github.com/careercup/CtCI-6th-Edition/tree/master/Java/Ch%2017.%20Hard/Q17_22_Word_Transformer
we've used an additional class BFSData. BFSData helps us keep things a bit clearer, and allows us to keep a similar framework for the two simultaneous breadth-first searches
public Queue<PathNode> toVisit = new LinkedList<PathNode>();
public HashMap<String, PathNode> visited = new HashMap<String, PathNode>();
public BFSData(String root) {
PathNode sourcePath = new PathNode(root, null);
toVisit.add(sourcePath);
visited.put(root, sourcePath);
}
public boolean isFinished() {
return toVisit.isEmpty();
}
}
public class PathNode {
private String word = null;
private PathNode previousNode = null;
public PathNode(String word, PathNode previous) {
this.word = word;
previousNode = previous;
}
public String getWord() {
return word;
}
/* Traverse path and return linked list of nodes. */
public LinkedList<String> collapse(boolean startsWithRoot) {
LinkedList<String> path = new LinkedList<String>();
PathNode node = this;
while (node != null) {
if (startsWithRoot) {
path.addLast(node.word);
} else {
path.addFirst(node.word);
}
node = node.previousNode;
}
return path;
}
}
public static LinkedList<String> transform(String startWord, String stopWord, String[] words) {
HashMapList<String, String> wildcardToWordList = getWildcardToWordList(words);
BFSData sourceData = new BFSData(startWord);
BFSData destData = new BFSData(stopWord);
while (!sourceData.isFinished() && !destData.isFinished()) {
/* Search out from source. */
String collision = searchLevel(wildcardToWordList, sourceData, destData);
if (collision != null) {
return mergePaths(sourceData, destData, collision);
}
/* Search out from destination. */
collision = searchLevel(wildcardToWordList, destData, sourceData);
if (collision != null) {
return mergePaths(sourceData, destData, collision);
}
}
return null;
}
/* Search one level and return collision, if any. */
public static String searchLevel(HashMapList<String, String> wildcardToWordList, BFSData primary, BFSData secondary) {
/* We only want to search one level at a time. Count how many nodes are currently in the primary's
* level and only do that many nodes. We'll continue to add nodes to the end. */
int count = primary.toVisit.size();
for (int i = 0; i < count; i++) {
/* Pull out first node. */
PathNode pathNode = primary.toVisit.poll();
String word = pathNode.getWord();
/* Check if it's already been visited. */
if (secondary.visited.containsKey(word)) {
return pathNode.getWord();
}
/* Add friends to queue. */
ArrayList<String> words = getValidLinkedWords(word, wildcardToWordList);
for (String w : words) {
if (!primary.visited.containsKey(w)) {
PathNode next = new PathNode(w, pathNode);
primary.visited.put(w, next);
primary.toVisit.add(next);
}
}
}
return null;
}
public static LinkedList<String> mergePaths(BFSData bfs1, BFSData bfs2, String connection) {
PathNode end1 = bfs1.visited.get(connection); // end1 -> source
PathNode end2 = bfs2.visited.get(connection); // end2 -> dest
LinkedList<String> pathOne = end1.collapse(false); // forward: source -> connection
LinkedList<String> pathTwo = end2.collapse(true); // reverse: connection -> dest
pathTwo.removeFirst(); // remove connection
pathOne.addAll(pathTwo); // add second path
return pathOne;
}
public static LinkedList<String> transform(String start, String stop, String[] words) {
HashMapList<String, String> wildcardToWordList = createWildcardToWordMap(words);
HashSet<String> visited = new HashSet<String>();
return transform(visited, start, stop, wildcardToWordList);
}
/* Do a depth-first search from start to stop, traveling through each word that is one edit away. */
public static LinkedList<String> transform(HashSet<String> visited, String start, String stop, HashMapList<String, String> wildcardToWordList) {
if (start.equals(stop)) {
LinkedList<String> path = new LinkedList<String>();
path.add(start);
return path;
} else if (visited.contains(start)) {
return null;
}
visited.add(start);
ArrayList<String> words = getValidLinkedWords(start, wildcardToWordList);
for (String word : words) {
LinkedList<String> path = transform(visited, word, stop, wildcardToWordList);
if (path != null) {
path.addFirst(start);
return path;
}
}
return null;
}
/* Insert words in dictionary into mapping from wildcard form -> word. */
public static HashMapList<String, String> createWildcardToWordMap(String[] words) {
HashMapList<String, String> wildcardToWords = new HashMapList<String, String>();
for (String word : words) {
ArrayList<String> linked = getWildcardRoots(word);
for (String linkedWord : linked) {
wildcardToWords.put(linkedWord, word);
}
}
return wildcardToWords;
}
/* Get list of wildcards associated with word. */
public static ArrayList<String> getWildcardRoots(String w) {
ArrayList<String> words = new ArrayList<String>();
for (int i = 0; i < w.length(); i++) {
String word = w.substring(0, i) + "_" + w.substring(i + 1);
words.add(word);
}
return words;
}
/* Return words that are one edit away. */
public static ArrayList<String> getValidLinkedWords(String word, HashMapList<String, String> wildcardToWords) {
ArrayList<String> wildcards = getWildcardRoots(word);
ArrayList<String> linkedWords = new ArrayList<String>();
for (String wildcard : wildcards) {
ArrayList<String> words = wildcardToWords.get(wildcard);
for (String linkedWord : words) {
if (!linkedWord.equals(word)) {
linkedWords.add(linkedWord);
}
}
}
return linkedWords;
}
public static ArrayList<String> wordsOneAway(String word) {
ArrayList<String> words = new ArrayList<String>();
for (int i = 0; i < word.length(); i++) {
for (char c = 'a'; c <= 'z'; c++) {
String w = word.substring(0, i) + c + word.substring(i + 1);
words.add(w);
}
}
return words;
}
public static LinkedList<String> transform(HashSet<String> visited, String startWord, String stopWord, Set<String> dictionary) {
if (startWord.equals(stopWord)) {
LinkedList<String> path = new LinkedList<String>();
path.add(startWord);
return path;
} else if (visited.contains(startWord) || !dictionary.contains(startWord)) {
return null;
}
visited.add(startWord);
ArrayList<String> words = wordsOneAway(startWord);
for (String word : words) {
LinkedList<String> path = transform(visited, word, stopWord, dictionary);
if (path != null) {
path.addFirst(startWord);
return path;
}
}
return null;
}
public static LinkedList<String> transform(String start, String stop, String[] words) {
HashSet<String> dict = setupDictionary(words);
HashSet<String> visited = new HashSet<String>();
return transform(visited, start, stop, dict);
}
public static HashSet<String> setupDictionary(String[] words) {
HashSet<String> hash = new HashSet<String>();
for (String word : words) {
hash.add(word.toLowerCase());
}
return hash;
}
https://scyforce.gitbooks.io/leetcode/content/word_ladder_ii.html
private void getNextWords(Map<String, Set<String>> nextWordsMap, String word, Set<String> dict) {
char [] chars = word.toCharArray();
for (int i = 0; i < word.length(); i++) {
char old = chars[i];
for (char c = 'a'; c <= 'z'; c++) {
//do not add the current word
if (c != old) {
chars[i] = c;
String nextWord = new String(chars);
if (dict.contains(nextWord)) {
Set<String> nextWords = nextWordsMap.get(word);
if (nextWords != null) {
nextWords.add(nextWord);
} else {
nextWords = new HashSet<String>();
nextWords.add(nextWord);
nextWordsMap.put(word, nextWords);
}
}
}
}
//revert the word back
chars[i] = old;
}
}
public List<List<String>> findLadders(String start, String end, Set<String> dict) {
List<List<String>> results = new ArrayList<List<String>>();
Queue<String> queue = new LinkedList<String>();
Map<String, Integer> levelMap = new HashMap<String, Integer>();
queue.add(start);
levelMap.put(start, 1);
//make sure the end is in dict
dict.add(end);
Map<String, Set<String>> nextWordsMap = new HashMap<String, Set<String>>();
getNextWords(nextWordsMap, start, dict);
// init adjacent graph
for(String word : dict){
getNextWords(nextWordsMap, word, dict);
}
while (!queue.isEmpty()) {
String wordPath = queue.poll();
String[] words = wordPath.split(" ");
String current = words[words.length-1];
if (current.equals(end)) {
List<String> result = Arrays.asList(words);
results.add(result);
} else {
Set<String> nextWords = nextWordsMap.get(current);
if (nextWords!=null) {
int nextLevel = words.length+1;
for (String nextWord : nextWords) {
//if the word has been used before then he can only be added to the same level
if (levelMap.get(nextWord)==null || nextLevel==levelMap.get(nextWord)) {
queue.add(wordPath + " " + nextWord);
if (levelMap.get(nextWord)==null) {
levelMap.put(nextWord, nextLevel);
}
}
}
}
}
}
return results;
}https://discuss.leetcode.com/topic/7387/java-solution-with-iteration
TODO: http://siyang2leetcode.blogspot.com/2015/01/word-ladder-ii.html
https://discuss.leetcode.com/topic/9156/java-modified-bfs-to-find-end-followed-by-dfs-to-reconstruct-paths
Read full article from LeetCode:Word Ladder I II - tenos - 博客园
