单词接龙（BFS实现）

题目

给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：

每次转换只能改变一个字母；转换过程中的中间单词必须是字典中的单词。

说明:

如果不存在这样的转换序列，返回 0；所有单词具有相同的长度；所有单词只由小写字母组成；字典中不存在重复的单词；你可以假设 beginWord 和 endWord 是非空的，且二者不相同。

示例 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” 不在字典中，所以无法进行转换。

注意点

1、将字典转为set集合，便于判断单词是否存在字典中； 2、选择获取符合要求单词的方式：

将当前单词与字典中的所有单词进行比较，获取只有一个字母差距的单词需要O(n * m)（n为字典中单词的数量，m为单词的长度）的时间复杂度；将当前单词的每一位替换成”a - z“，判断是否在字典中，只需要O(26 * m)（m为单词的长度）的时间复杂度，所以我们采取这一种方式。

3、必须记录访问过的单词，避免bfs出现死循环；（因为转换是可逆的，如hot可以变成dot，dot也可以变成hot） 4、处理每一个单词时，必须保存原来位置的字符。（因为后面循环需要使用原单词）

实现

public int ladderLength(String beginWord, String endWord, List<String> wordList) { // 将字典转为set集合，便于判断单词是否存在字典中 Set<String> wordSet = new HashSet<>(wordList); // 判断字典是否存在结束单词 if (!wordSet.contains(endWord)) { return 0; } return dfs(beginWord, endWord, wordSet); } public int dfs(String beginWord, String endWord, Set<String> wordSet) { // 队列，存放每一层符合要求的单词 Queue<String> queue = new LinkedList<>(); // 初始化队列，默认为开始单词 queue.offer(beginWord); // 记录访问过的单词，避免bfs出现死循环 Set<String> visited = new HashSet<>(); // 初始化集合，默认为开始单词 visited.add(beginWord); // 初始化长度为1（开始单词） int step = 1; // 判断每一层是否存在符合要求的单词 while (!queue.isEmpty()) { // 每一层符合要求单词的数量 int queueSize = queue.size(); // 处理每一层每一个单词 for (int i = 0; i < queueSize; i ++) { // 获取每一层的每一个单词 String curWord = queue.poll(); char[] curCharArray = curWord.toCharArray(); // 处理每一个单词的所为位 for (int j = 0; j < curCharArray.length; j ++) { // 保存单词每一位的原始值 char orgin = curCharArray[j]; // 将每一位替换成a - z for (char k = 'a'; k <= 'z'; k ++) { // 剪枝，如果是原字符，直接跳过 if (k == orgin) { continue; } // 获得符合要求的下一个单词 curCharArray[j] = k; String nextWord = String.valueOf(curCharArray); // 判断下一个单词是否存在字典中 if (wordSet.contains(nextWord)) { // 判断下一个单词是否为结束单词 if (nextWord.equals(endWord)) { // 直接返回长度 return step + 1; } // 判断下一个单词是否访问过，避免死循环 if (!visited.contains(nextWord)) { // 更新队列（下一层符合要求的单词） queue.offer(nextWord); // 更新访问集合 visited.add(nextWord); } } } // 将单对应位置为原来的值 curCharArray[j] = orgin; } } // 每一层处理完，长度加1 step ++; } // 不存在符合要求的路径 return 0; }