127. 单词接龙
题目
给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：
每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。
说明:
如果不存在这样的转换序列，返回 0。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
解题思路
这题求最短转换序列的长度，当然用BFS。这题难点有2.
①画出无向图 ②根据什么条件找到邻居节点
我之前想到一种方法是用beginword和wordlist中的每一个字符串相比较，如果只有一个字符不同那么beginword和它之间就有连线， 同理beginword的邻居节点的邻居节点也用这个方法求。但是这样做有问题，当wordlist一大了之后就会超出时间限制。
所以换一个思路，用一个Hash表把所有的单词列表放进一个哈希表中，借助哈希表【复杂度是O(26×wordLen)】，找到邻居与 N 【这里 N 是单词列表的长度】无关，所以不会超时
例如beginword是“hit”，我们一开始只要用a-z替换hit的h，看hash表是否有符合的，如果没有，再用a-z替换i，以此类推
代码
没有抽取方法版本
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Queue<String> queue = new LinkedList<>();
List<String> visited = new ArrayList<>();
Set<String> wordSet = new HashSet<>(wordList);//把wordList放入Hash表中，用来比较遍历，如果直接和wordlist来比较会超时
if (!wordSet.contains(endWord)) {
return 0;
}
wordSet.remove(beginWord);
queue.add(beginWord);
visited.add(beginWord);
int step = 0;
while (!queue.isEmpty()) {
step++;
int size = queue.size();
while (size-- > 0) {
String poll = queue.poll();
// 如果 poll 能够修改 1 个字符与 endWord 相同，证明它俩有连线，走出那一步即可，即返回 step + 1(走出的那一步)
char[] charArray = poll.toCharArray();//把当前字符串拆成字符数组，便于替换
for (int i = 0; i < endWord.length(); i++) {
// 先保存，然后恢复，即一轮后要重置该字符串
char originChar = charArray[i];//因为每次只能替换一个字符，所以要保存一个原本。
for (char k = 'a'; k <= 'z'; k++) {//遍历a-z
if (k == originChar) {//即Hash表中遇到了和beginword一样的字符串，直接跳过
continue;
}
charArray[i] = k;//替换一个字符
String nextWord = String.valueOf(charArray);//替换后的字符串
if (wordSet.contains(nextWord)) {//即 beginword和hash表中的某字符串只有一个字符不同，它们之间生成连线
if (nextWord.equals(endWord)) {//符合条件，直接返回
return step + 1;//因为nextWord.equals(endWord)只是找到了它和endword之间有连线，还没有迈出那一步，需要迈出那一步才能到endword
}
if (!visited.contains(nextWord)) {//找它的邻居节点
queue.add(nextWord);
// 注意：添加到队列以后，必须马上标记为已经访问
visited.add(nextWord);
}
}
}
// 恢复
charArray[i] = originChar;
}
}
}
return 0;
}
}
抽取了方法的版本
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Queue<String> queue = new LinkedList<>();
List<String> visited = new ArrayList<>();
Set<String> wordSet = new HashSet<>(wordList);
if (!wordSet.contains(endWord)) {
return 0;
}
wordSet.remove(beginWord);
queue.add(beginWord);
visited.add(beginWord);
int step = 0;
while (!queue.isEmpty()) {
step++;
int size = queue.size();
while (size-- > 0) {
String poll = queue.poll();
// 如果 currentWord 能够修改 1 个字符与 endWord 相同，则返回 step + 1
if (changeWordEveryOneLetter(poll, endWord, queue, visited, wordSet)) {
return step + 1;
}
}
}
return 0;
}
/**
* 尝试对 currentWord 修改每一个字符，看看是不是能与 endWord 匹配
*/
private boolean changeWordEveryOneLetter(String currentWord, String endWord,
Queue<String> queue, List<String> visited, Set<String> wordSet) {
char[] charArray = currentWord.toCharArray();
for (int i = 0; i < endWord.length(); i++) {
// 先保存，然后恢复
char originChar = charArray[i];
for (char k = 'a'; k <= 'z'; k++) {
if (k == originChar) {
continue;
}
charArray[i] = k;
String nextWord = String.valueOf(charArray);
if (wordSet.contains(nextWord)) {
if (nextWord.equals(endWord)) {
return true;
}
if (!visited.contains(nextWord)) {
queue.add(nextWord);
// 注意：添加到队列以后，必须马上标记为已经访问
visited.add(nextWord);
}
}
}
// 恢复
charArray[i] = originChar;
}
return false;
}
}
本题与111题step的区别
力扣111和127达到目标后一个返回step一个返回step+1的原因
111
第一次把根节点1放入队列，step加一，然后发现它有子节点，继续，先把左边子节点放入队列，step加一，无子节点了，达到目标，走了两步，返回step刚好，即队列最后弹出的那个元素即为我们求的那个元素，所以只返回step
127
第一次把hit放入队列step加一，然后发现hit和hot有连线，走出那一步即step加一，然后发现bot与它有连线（到这里，判断已经结束了，已经找到符合条件的hot了，不会进行下一个循环了，但是还只替换，并没有迈出那一步）所以需要返回step加一，而不是step。
即在队列最后一次弹出的不是目标元素，而是目标元素的前一个
