网站开发工程师资格证/百度推广关键词质量度

1. 问题描述：

给定两个单词（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" 不在字典中，所以无法进行转换。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-ladder

2. 思路分析：

① 根据题目可以知道，这个是比较经典的bfs搜索，因为我们可以知道原始状态已经给出来了，目标状态也已经给出来了，而且求解的为原始状态到目标状态的最短路径，这个是经典实用bfs求解的题目，在一开始的时候我是创建了一个内部类，里面封装了几个属性：

1）到达当前状态的字符串是什么

2）到达当前状态的步数

3）一个用来记录到达当前状态字典中的哪些位置已经被访问的字符串

② 一开始的时候加入开始的单词，并且初始化当前状态下字典中单词访问标志的字符串，将这个节点加入到队列中，在循环中弹出节点，对当前的节点逐位进行判断，看一下字典中哪些单词是改变一位之后是符合的，符合的话将当前状态下的标记字典中该位已经被访问的，而且将当前的这个单词加入到队列中，其实思路还是很好理解的，但是在提交的时候超时了，只是通过了20多个数据，这个也不难理解，因为bfs在极端情况下也会出现很多个分支即指数级增长，那么在搜索的时候就会非常慢了

③ 在看了官方的题解之后发现真的是自己写的比较low哎，感觉他们的思路真的是非常好，一种比较好理解的方法思路如下：

它是将给出的单词先做一个预处理，比如 "hot","dot","dog","lot","log","cog"，遍历每一个单词，比如对于hot单词对于每一位使用*进行占位，变成三个对应的字符串，*ot，h*t，ho*，对于其他的单词也是一样的道理

并且最核心的是使用一个Map来来映射这写字符串，键为占位符，比如为*ot，值的类型为ArrayList，ArrayList连接所有的占位符一样的单词，这样的话就把所有的*ot对应的单词连接起来

*ot {

hot

lot

}

这个思路真的是非常好，我们在标记当前的单词是否已经被访问了那么可以直接通过Map来进行判断，map封装占位符对应的字符串，值为布尔值，这样在访问遍历完当前的占位符对应的字符串会将所有的对应的单词遍历完

思路非常好而且易于理解，其中在遍历List的时候使用了java 8的某些遍历语法可以学习一下，还有一种方法比较难理解就是双端bfs了，这个可以参照官方的题解看一下了，感觉还是比较难理解

3. 代码如下

我自己写的代码（超时了）

import java.util.*;
public class Solution {public class Node{/*到达当前状态使用过的位置, 使用字符串比使用数组要方便*/String visStr = "";/*当前状态对应的字符串*/String cur;/*到达当前状态下的步骤*/int step;/*构造器用来初始化*/public Node(String cur, int vislen) {this.cur = cur;/*在新建节点的时候创建标记数组*/for (int i = 0; i < vislen; ++i){this.visStr += "0";}}public Node(String cur, int step, String visStr) {this.cur = cur;this.step = step;this.visStr = visStr;}public String getVisStr() {return visStr;}public void setVisStr(String visStr) {this.visStr = visStr;}/*设置某一个位置的字母被使用*/public void setPosIndex(int index){visStr = visStr.substring(0, index) + "1" + visStr.substring(index + 1);}public String getCur() {return cur;}public void setCur(String cur) {this.cur = cur;}public int getStep() {return step;}public void setStep(int step) {this.step = step;}}public int ladderLength(String beginWord, String endWord, List<String> wordList) {if (!wordList.contains(endWord)) return 0;/*这里要特别注意是一个字母的情况比如这样: a c abc*/if (beginWord.length() == 1 && wordList.contains(endWord)) return 2;int len = beginWord.length();int visLen = wordList.size();Node start = new Node(beginWord, visLen);Queue<Node> queue = new LinkedList();queue.add(start);while (!queue.isEmpty()){/*当前状态下的字符串*/Node poll = queue.poll();if (poll.getCur().equals(endWord))return poll.step + 1;String cur = poll.getCur();String curVis = poll.getVisStr();for (int i = 0; i < len; ++i){String t = "";t = cur.substring(0, i) + cur.substring(i + 1);for (int j = 0; j < wordList.size(); ++j){if (!wordList.get(j).equals(beginWord) && curVis.charAt(j) == '0'){if ((wordList.get(j).substring(0, i) + wordList.get(j).substring(i + 1)).equals(t)){Node newNode = new Node(wordList.get(j), poll.getStep() + 1, poll.getVisStr());/*设置当前的位置已被访问*/newNode.setPosIndex(j);queue.add(newNode);}}}}}return 0;}
}

预处理之后的代码：

import java.util.*;
public class Solution {public int ladderLength(String beginWord, String endWord, List<String> wordList) {int L = beginWord.length();HashMap<String, ArrayList<String>> allComboDict = new HashMap<String, ArrayList<String>>();wordList.forEach(word -> {for (int i = 0; i < L; i++) {String newWord = word.substring(0, i) + '*' + word.substring(i + 1, L);/*getOrDefault假如有值获取其中的值没有值的话获取默认的值*/ArrayList<String> transformations = allComboDict.getOrDefault(newWord, new ArrayList<String>());transformations.add(word);allComboDict.put(newWord, transformations);}});Queue<Pair<String, Integer>> Q = new LinkedList<Pair<String, Integer>>();Q.add(new Pair(beginWord, 1));HashMap<String, Boolean> visited = new HashMap<String, Boolean>();visited.put(beginWord, true);while (!Q.isEmpty()) {Pair<String, Integer> node = Q.remove();String word = node.getKey();int level = node.getValue();for (int i = 0; i < L; i++) {String newWord = word.substring(0, i) + '*' + word.substring(i + 1, L);for (String adjacentWord : allComboDict.getOrDefault(newWord, new ArrayList<String>())) {if (adjacentWord.equals(endWord)) {return level + 1;}if (!visited.containsKey(adjacentWord)) {visited.put(adjacentWord, true);Q.add(new Pair(adjacentWord, level + 1));}}}}return 0;}
}