LeetCode--127. Word Ladder_leetcode word-ladde

题目链接：https://leetcode.com/problems/word-ladder/

给定一个起始单词和目标单词和一个单词字典，每次对起始单词只能进行一个字母的变化，并且变化后的单词要么存在于字典中，要么起始单词变成了目标单词。并且题目要求返回最少变化的次数。这个题意比较绕，但理解不困难。举个例子：

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

one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog"

看了这个例子问题来了，应该怎么变？没有规则呀？那就暴力搜索呗！暴力搜索需要考虑所有情况，假设字符串长度为n，每次变化的位置可以是[0,n-1]，以前变化过的位置在本次也可以变化。另外变成的新字符范围是['a','z']。搜索应该以怎样的方式进行呢？DFS（递归）？BFS？这两个好像都可以。讨论完了变化的范围，我们需要解决一下最小变化次数的问题，相当于最小的步长，把一次变化的过程是从一个合法状态跳转到另外的一个合法状态的过程，每次跳转就是DFS里递归函数的依次调用，或者理解为图论算法里某个节点转到它的某个邻接节点上。这时我们想到了“单源多目标的最短路径算法”——BFS。这里BFS的过程可以参考二叉树的层次遍历（https://blog.csdn.net/To_be_to_thought/article/details/85683388）和图的硬拷贝算法（https://blog.csdn.net/To_be_to_thought/article/details/85344694），这个题本质就是个图论题而不是字符串题。先用这两个来找找BFS的感觉。类似于树的层次遍历，每次队列的弹出次数是由上一层次所有父节点的子节点总数决定的。对于上面的例子，第一层来说就只要有一个节点（起始单词），第二层就是改变一个字符后且存在于字典中的的单词们。这里要注意改变后的单词要跟他的父节点的单词不一样，否则就陷入带环有向图的死循环了。另外，就是一个节点只需要访问一次就够了，其他节点的转变使得再次跳转到已经访问过的节点时造成不必要的重复，所以要动态更新字典。

代码如下：

class Solution {
 
    public static HashSet<String> set;
    
    public int ladderLength(String beginWord, String endWord, List<String> wordList) 
    {
        
        set=new HashSet();
        for(String s:wordList)
            set.add(s);
        set.add(beginWord);
        Queue<String> queue = new LinkedList<String>();
        queue.add(beginWord);
        int level = 0;
        while(!queue.isEmpty())
        {
            int size = queue.size();
            for(int i = 0; i < size; i++)
            {
                String cur = queue.remove();
                if(cur.equals(endWord))
                    return level + 1;
                for(int j = 0; j < cur.length(); j++)
                {
                    char[] word = cur.toCharArray();
                    for(char ch = 'a'; ch < 'z'; ch++)
                    {
                        word[j] = ch;
                        String check = new String(word);
                        if(!check.equals(cur) && set.contains(check))
                        {
                            queue.add(check);
                            set.remove(check);
                        }
                    }
                }
            }
            level++;
        }
        return 0;
    }
}