Word Ladder II

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/

Solution:

https://leetcode.com/discuss/64808/my-concise-java-solution-based-on-bfs-and-dfs

public List findLadders(String start, String end, Set<String> dict) { List res = new ArrayList(); HashMap nodeNeighbors = new HashMap();// Neighbors for every node HashMap distance = new HashMap();// 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 nodeNeighbors, HashMap 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 nodeNeighbors, HashMap distance, ArrayList<String> solution, List 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); }