米哈游笔试原题，网友直呼太难！
米哈游笔试原题，网友直呼太难！
这道题是力扣的第127题，难度为困难，一网友在米哈游的笔试中遇到这题。实际上这题的代码量还挺多的，如果是在机试上直接敲代码我还能理解，但在笔试中没有任何代码提示的情况下能把它完整的写出来真的是不容易。
还有其他网友直呼太难。。。
还有在其他的面试中也遇到过。
问题描述
来源：LeetCode第127题
难度：困难
这题说的是给定两个字符串beginWord和endWord，每次只能改变字符串中的一个字符，让他成为一个新的字符串，并且这个新字符串必须存在于集合wordList中，问至少需要多少步可以从beginWord变成endWord，如果不能从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" 不在字典中，所以无法进行转换。
提示：
- endWord.length == beginWord.length
- wordList[i].length == beginWord.length
- beginWord、endWord 和 wordList[i] 由小写英文字母组成
- beginWord != endWord
- wordList 中的所有字符串互不相同
BFS解决
题中说了单词是由小写字母组成，所以单词中的每个字符有25种变化（小写字母有26个，但不能变成自己，否则等于没变），我们就按照这个思路改变单词中的每个字符然后构成一个新的单词，如果这个新的单词存在于字典中并且又没有被访问过我们就可以把它当做树的一个节点，添加到队列中，我们以示例1为例来画个图看下，这棵树我把它横着放了。
来看下代码：
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
// 把字典中的单词放入到set中，主要是为了方便查询
Set<String> dictSet = new HashSet<>(wordList);
Set<String> visited = new HashSet<>();
Queue<String> queue = new LinkedList<>();
queue.add(beginWord);// 把起始点添加到队列中
int level = 0;
while (!queue.isEmpty()) {
int levelCount = queue.size();// 当前层的节点个数
level++;// 第几层
// 遍历当前层的所有字符串
while (levelCount-- > 0) {
String word = queue.poll();
// 下面是修改字符串的字符，然后生成一个新的字符串
for (int j = 0; j < word.length(); j++) {
char[] ch = word.toCharArray();
for (char c = 'a'; c <= 'z'; c++) {
if (c == word.charAt(j))
continue;
ch[j] = c;
// 修改其中的一个字符，然后重新构建一个新的单词
String newWord = String.valueOf(ch);
// 如果字典中包含newWord，并且newWord没有被访问过，就把他加入到队列中
if (dictSet.contains(newWord) && visited.add(newWord)) {
// 加入队列之前判断newWord是不是我们要找的，如果是就直接返回
if (newWord.equals(endWord))
return level + 1;
queue.add(newWord);
}
}
}
}
}
return 0;
}
双向BFS解决
上面的只是通过一个方向查找，就是从起点到终点，如果字典中字符串比较多的话，这棵树是非常胖的，如下图所示。
如果要查找到endWord字符串我们需要遍历图中阴影部分的所有节点，可以看到这个节点非常多。我们来逆向思维一下，如果endWord字符串不在字典中我们肯定是查找不到的，直接返回0即可。如果endWord字符串在字典中我们可以用endWord作为根节点逆向查找，如下所示。
可以看到上面图中两棵树的公共部分明显比一棵树的小很多。图中的这两棵树我们都可以遍历，每次都只能遍历其中的一棵并且每次只能遍历一层，哪层节点少我们就先遍历哪层，当在某一层他们有公共字符串的时候，只需要返回这两棵树的高度和即可，我们画个图看下
对于两棵树的高度和我们可以使用一个变量levelTotal来记录，无论那棵树，只要遍历一层，levelTotal就加1。至于某一层他们是否有公共字符串，我们可以一边遍历一边查询，比如遍历第一棵树的时候我们需要在第二棵树中查询，遍历第二棵树的时候需要在第一棵树中查询，来看下代码：
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
// 这里要注意，如果endWord字符串不在字典中，无论怎么转换都不行的
if (!wordList.contains(endWord))
return 0;
Set<String> dictSet = new HashSet<>(wordList);
Set<String> visit = new HashSet<>();
// 创建两个队列
Queue<String> startQueue = new LinkedList<>();
Queue<String> endQueue = new LinkedList<>();
startQueue.add(beginWord);
endQueue.add(endWord);
int levelTotal = 1;
while (!startQueue.isEmpty() && !endQueue.isEmpty()) {
boolean res;
// 从少的开始遍历
if (startQueue.size() <= endQueue.size()) {
// 先遍历start树，然后在end树中查询
res = bfs(startQueue, endQueue, dictSet, visit);
} else {
// 先遍历end树，然后在start树中查询
res = bfs(endQueue, startQueue, dictSet, visit);
}
levelTotal++;// 遍历一层levelTotal就加1
// 如果返回true，说明在某一层有公共的字符串，直接返回总的访问层数levelTotal
if (res) return levelTotal;
}
return 0;
}
// 每次只能遍历一层，第一个队列是需要遍历的，第二个队列是待查询的
public boolean bfs(Queue<String> queue, Queue<String> query,
Set<String> dictSet, Set<String> visited) {
int levelCount = queue.size();// 当前队列中元素的个数
while (levelCount-- > 0) {
String word = queue.poll();
// 下面是修改字符串的字符，然后生成一个新的字符串
for (int j = 0; j < word.length(); j++) {
char[] ch = word.toCharArray();
for (char c = 'a'; c <= 'z'; c++) {
if (c == word.charAt(j))
continue;
ch[j] = c;
// 修改其中的一个字符，然后重新构建一个新的单词
String newWord = String.valueOf(ch);
// 新的字符串是否存在字典中
if (dictSet.contains(newWord)) {
// queue可以看做当前树的某一层的集合，
// query是另一棵树某一层的集合。
if (query.contains(newWord))
return true;
if (visited.add(newWord))
queue.offer(newWord);
}
}
}
}
return false;
}
腾讯云开发者
