public class Solution { public List<List<String>> findLadders(String start, String end, List<String> words) { /** 核心思路是倒序拍 end--> list of word can to end to end word --> list of word to this word ... to begin */ Set<String> dict = new HashSet<>(words); List<List<String>> res = new ArrayList<List<String>>(); if(start.compareTo(end) == 0) return res; Set<String> visited = new HashSet<String>(); Set<String> cur = new HashSet<String>(); HashMap<String, ArrayList<String>> graph = new HashMap<String, ArrayList<String>>(); graph.put(end,new ArrayList<String>()); cur.add(start); boolean found = false; while (!cur.isEmpty() && found == false) { Set<String> queue = new HashSet<String>(); //next level queue for(String word : cur) { visited.add(word); } for(String str : cur) { char[] word = str.toCharArray(); for (int j = 0; j < word.length; ++j) { char before = word[j]; for (char ch = 'a'; ch <= 'z'; ++ch) { if (ch == before) continue; word[j] = ch; String temp = new String(word); if (!dict.contains(temp)) continue; if (found == true && end.compareTo(temp) != 0) continue; //not the shortest path if (end.compareTo(temp) == 0) { found = true; (graph.get(end)).add(str); continue; } if (!visited.contains(temp)) { queue.add(temp); if (!graph.containsKey(temp)) { ArrayList<String> l = new ArrayList<String>(); l.add(str); graph.put(temp,l); } else { (graph.get(temp)).add(str); } } } word[j] = before; } } cur = queue; } if (found == true) { ArrayList<String> path = new ArrayList<String>(); trace(res, graph, path, start, end); } return res; } public void trace(List<List<String>> res, HashMap<String, ArrayList<String>> graph, ArrayList<String> path, String start, String now) { path.add(now); if (now.compareTo(start) == 0) { ArrayList<String> ans = new ArrayList<String>(path); Collections.reverse(ans); res.add(ans); path.remove(path.size() - 1); return; } ArrayList<String> cur = graph.get(now); for (int i = 0; i < cur.size(); ++i) { trace(res,graph,path,start,cur.get(i)); } path.remove(path.size()-1); } }