题目描述

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

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

说明:

• 如果不存在这样的转换序列，返回 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" 不在字典中，所以无法进行转换。

https://leetcode-cn.com/problems/word-ladder/

解法1

解法1使用BFS，为什么是Search解法呢？因为题目提示了，单词具有相同的长度，且只有小写字母，这样我们变换单词的每个字符就能形成新的单词，而不需要增删单词。为什么是BFS而不是DFS呢？因为要求最短转换序列，而BFS能够保证路径最短。如果我们使用DFS搜单词变化的路径，假设有两条长度不同的路径都能到达endWord，那么使用DFS可能先走入长路径，我们需要寻找出所有可行的路径，然后取他们最短的一个；而BFS是按照层次来搜索的，只要是遇到endWord，发现的路径一定是最短的。

那么搜索思路是什么呢？我们创建一个Queue，将beginWord加入队列。然后从队列中取出word，我们每次改变word的每个字符。因为字典里保存的单词都是小写字母，我们对每个字符枚举’a’ – ‘z’即可，然后检查新形成的单词是否存在于字典中。如果新单词存在于字典中，那么说明这个单词是中间单词，我们把他加入队列中，并从字典中移除；如果这个单词在字典中，且和endWord相等，那么我们就找到了最短路径。

例1：

beginWord = "hit", 
endWord = "cog", 
wordList = ["hot","dot","dog","lot","log","cog"]

图1描述了BFS的过程，从hit作为beginWord开始，我们修改word的每一个字符，字符的变化范围是’a’-‘z’。如果形成的新的单词在wordList中存在，那么新单词就是变化路径的节点；如果新形成的单词不光在wordList中存在，且与endWord相等，那么我们就成功找到了一条转换序列。

为什么要从字典移除发现的单词呢？如果不从字典中移除，那么我们可能会出现a-b-a的情况，走了“回头路”，使得找到的路径不是最短路径。

令一点需要注意的是，题目要求计算的是转化序列的长度，而不是经过了几步变换。令一点需要注意的是，实现BFS时从queue取元素那个for循环应该逆序，这样我们才能够取得同一层次的word。如果我们顺序遍历，每次循环都会调用queue.size()，而在循环过程中queue的size是不断变化的，导致逻辑错误。如果想让for循环写法是顺序的，就要用另一个变量保存queue被修改前的长度，这样我们才能够访问同一层次的word。

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Queue<String> queue = new LinkedList<>();
        Set<String> wordSet = new HashSet<>(wordList);
        int step = 0;

        wordSet.remove(beginWord);
        queue.offer(beginWord);

        while (queue.size() > 0) {
            step++;

            for (int i = queue.size(); i > 0; i--) {
                char[] word = queue.poll().toCharArray();

                for (int x = 0; x < word.length; x++) {
                    char originC = word[x];

                    for (char c = 'a'; c <= 'z'; c++) {
                        word[x] = c;
                        String newWord = new String(word);

                        if(wordSet.contains(newWord)) {
                            if (newWord.equals(endWord))
                                return step + 1;

                            wordSet.remove(newWord);
                            queue.offer(newWord);
                        }
                    }

                    word[x] = originC;
                }
            }
        }

        return 0;
    }
}