题目：单词接龙 II hard
给定两个单词（beginWord 和 endWord）和一个字典 wordList， 找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则： 每次转换只能改变一个字母。 转换后得到的单词必须是字典中的单词。
说明: 如果不存在这样的转换序列，返回一个空列表。 所有单词具有相同的长度。 所有单词只由小写字母组成。 字典中不存在重复的单词。 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
示例 1: 输入: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出: [ ["hit","hot","dot","dog","cog"], ["hit","hot","lot","log","cog"] ]
示例 2: 输入: beginWord = "hit" endWord = "cog" wordList = ["hot","dot","dog","lot","log"]
输出: [] 解释: endWord "cog" 不在字典中，所以不存在符合要求的转换序列。
package leetCode.BFS; import java.util.*; public class lc_bfs_126_findLadders { /* 思路： 1.dfs 超时 2.bfs 直接记录路径path，visited用来记录除了当前访问层外，所有的已经访问过的单词， subVisied是记录当前访问层的已访问单词，因为当前层可以重复访问同一个单词 */ /** * bfs * 直接记录路径path，visited用来记录除了当前访问层外，所有的已经访问过的单词， * subVisied是记录当前访问层的已访问单词，因为当前层可以重复访问同一个单词 */ public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) { ArrayDeque<List<String>> pathsQue = new ArrayDeque<>(); LinkedList<String> path = new LinkedList<>(); List<List<String>> ans = new LinkedList<>(); int indexOfendword = wordList.indexOf(endWord); if (indexOfendword == -1) {//没有就直接返回，不用查找了 return ans; } path.add(beginWord); pathsQue.offer(path); HashSet<String> dict = new HashSet<>(wordList); //用来记录除了当前访问层外，所有的已经访问过的单词， // subVisied是记录当前访问层的已访问单词，因为当前层可以重复访问同一个单词 HashSet<String> visited = new HashSet<>(); visited.add(beginWord); boolean isFound = false;//用来标记在该层已经找到结束单词，不要再遍历下一层了 while (!pathsQue.isEmpty()) { HashSet<String> subVisited = new HashSet<>(); int size = pathsQue.size(); for (int j = 0; j < size; j++) { List<String> curPath = pathsQue.poll(); //得到当前路径的末尾单词 String lastWord = curPath.get(curPath.size() - 1); if (lastWord.equals(endWord)) { isFound = true; ans.add(curPath); continue;//不要再扩展路径了，直接检查下一个，该层遍历完就结束 } // 一次性得到所有的下一个的节点 List<String> neighbors = getNeighbor(lastWord, dict); for (String n : neighbors) { //只考虑之前没有出现过的单词，前面层已经出现过的单词再次加入肯定不是最短的，剪枝了 if (!visited.contains(n)) { //加入当前单词 LinkedList<String> newPath = new LinkedList<>(curPath); newPath.add(n); pathsQue.offer(newPath); //加入当前访问层的已访问的单词，里面的元素和visited里的都不重复 subVisited.add(n); } } }//该层遍历完 visited.addAll(subVisited);//将当前层的已访问单词加入总的已访问单词 if (isFound) break;//找到后，当前层访问完就不要进行下一层循环，直接跳出返回 } return ans; } // 得到node结点的所有的下一个节点集合 public List<String> getNeighbor(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版本 */ int minLen = Integer.MAX_VALUE; public List<List<String>> findLadders2(String beginWord, String endWord, List<String> wordList) { ArrayList<List<String>> ans = new ArrayList<>(); boolean[] vis = new boolean[wordList.size()]; ArrayList<String> path = new ArrayList<>(); path.add(beginWord); dfs(beginWord, path, ans, vis, endWord, wordList); return ans; } public void dfs(String cur, List<String> path, List<List<String>> ans, boolean[] vis, String endWord, List<String> wordList) { if (cur.equals(endWord)) { if (path.size() <= minLen) { if (path.size() < minLen) // ans = new ArrayList<>(); ans.clear(); ans.add(new ArrayList<>(path)); minLen = path.size(); } return; } if (path.size() >= minLen) { return; } for (int i = 0; i < wordList.size(); i++) { String word = wordList.get(i); if (!vis[i] && isLike(cur, word)) { vis[i] = true; path.add(word); dfs(word, path, ans, vis, endWord, wordList); path.remove(path.size() - 1); vis[i] = false; } } } public boolean isLike(String a, String b) { int count = 0; for (int i = 0; i < a.length(); i++) { if (a.charAt(i) != b.charAt(i)) { count++; if (count > 1) return false; } } return true; } }
