127. 单词接龙

字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列：

序列中第一个单词是 beginWord 。
序列中最后一个单词是 endWord 。
每次转换只能改变一个字母。
转换过程中的中间单词必须是字典 wordList 中的单词。
给你两个单词 beginWord 和 endWord 和一个字典 wordList ，找到从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0。

 
示例 1：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：5
解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。
示例 2：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：0
解释：endWord "cog" 不在字典中，所以无法进行转换。

解法一：宽度优先搜索

class Solution { public int ladderLength(String beginWord, String endWord, List<String> wordList) { if (!wordList.contains(endWord)) { return 0; } Set<String> visited = new HashSet<>(); Queue<String> queue = new LinkedList<>(); queue.offer(beginWord); visited.add(beginWord); int count = 0; while (queue.size() > 0) { int size = queue.size(); ++count; for (int i = 0; i < size; ++i) { String start = queue.poll(); for (String s : wordList) { // 已经遍历的不再重复遍历 if (visited.contains(s)) { continue; } // 不能转换的直接跳过 if (!canConvert(start, s)) { continue; } // 用于调试 // System.out.println(count + ": " + start + "->" + s); // 可以转换，并且能转换成 endWord，则返回 count if (s.equals(endWord)) { return count + 1; } // 保存访问过的单词，同时把单词放进队列，用于下一层的访问 visited.add(s); queue.offer(s); } } } return 0; } public boolean canConvert(String s1, String s2) { if (s1.length() != s2.length()) return false; int count = 0; for (int i = 0; i < s1.length(); ++i) { if (s1.charAt(i) != s2.charAt(i)) { ++count; if (count > 1) { return false; } } } return count == 1; } } 。

解法二：双向宽度优先搜索

class Solution { public int ladderLength(String beginWord, String endWord, List<String> wordList) { int end = wordList.indexOf(endWord); if (end == -1) { return 0; } wordList.add(beginWord); // 从两端 BFS 遍历要用的队列 Queue<String> queue1 = new LinkedList<>(); Queue<String> queue2 = new LinkedList<>(); // 两端已经遍历过的节点 Set<String> visited1 = new HashSet<>(); Set<String> visited2 = new HashSet<>(); queue1.offer(beginWord); queue2.offer(endWord); visited1.add(beginWord); visited2.add(endWord); int count = 0; Set<String> allWordSet = new HashSet<>(wordList); while (!queue1.isEmpty() && !queue2.isEmpty()) { count++; if (queue1.size() > queue2.size()) { Queue<String> tmp = queue1; queue1 = queue2; queue2 = tmp; Set<String> t = visited1; visited1 = visited2; visited2 = t; } int size1 = queue1.size(); while (size1-- > 0) { String s = queue1.poll(); char[] chars = s.toCharArray(); for (int j = 0; j < s.length(); ++j) { // 保存第j位的原始字符 char c0 = chars[j]; for (char c = 'a'; c <= 'z'; ++c) { chars[j] = c; String newString = new String(chars); // 已经访问过了，跳过 if (visited1.contains(newString)) { continue; } // 两端遍历相遇，结束遍历，返回 count if (visited2.contains(newString)) { return count + 1; } // 如果单词在列表中存在，将其添加到队列，并标记为已访问 if (allWordSet.contains(newString)) { queue1.offer(newString); visited1.add(newString); } } // 恢复第j位的原始字符 chars[j] = c0; } } } return 0; } }

优化牛逼

网址：127. 单词接龙 https://mxgxt.com/news/view/924376

相关内容

词语接龙大全
词语接龙游戏,词语接龙规则:用成语前缀后缀扩展方法接龙
中国诗词大会，最简单又好玩的游戏――诗词接龙，你最多能对几句呢
240717 nct127红色tv更新 廷祐相关 视频一则 NCT 127 엔시티 127 삐그덕
词语接龙游戏怎么玩
歌词接龙的游戏规则（2页）
接龙
手机如何接龙
大悦相关单词
NBA巨星詹姆斯全明星赛佩戴百达翡丽127万名表

随便看看