WordLadder

https://leetcode.com/problems/word-ladder/
Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

人工翻译：给定一个beginword，一个endword，一个wordlist，从beginword开始，每次只能变动word中的一个字母，并且变动后的word必须在wordlist中，求出从beginword到endword的最短变换的路径

• 思路
  BFS大法好，BFS遍历的是什么呢？ 遍历的还"a~z"26个英文字母，从beginword开始，单词每一位都逐个遍历
  talk is cheap，show me your example
  以上图的实例，整个过程可以如下

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        HashSet<String> set = new HashSet<>(wordList);
        Queue<String> wordQueue = new LinkedList<String>();
        int level = 1;//最开始的string  就是level 为1 了
        int currnum = 1;//当前level有多少个单词
        int nextnum = 0;//下一个level的计数器
        wordQueue.add(beginWord);
        while (!wordQueue.isEmpty()) {
            String word = wordQueue.poll();
            currnum--;
            for (int i = 0; i < word.length(); i++) {
                char[] wordunit = word.toCharArray();
                for (char j = 'a'; j <= 'z'; j++) {
                    wordunit[i] = j;
                    String temp = new String(wordunit);

                    if (set.contains(temp)) {
                        if (temp.equals(endWord)) {
                            return level + 1;
                        }

                        nextnum++;
                        wordQueue.add(temp);
                        set.remove(temp);
                    }
                }
            }

            if (currnum == 0) {
                currnum = nextnum;
                nextnum = 0;
                level++;
            }
        }
        return 0;
    }

• 为什么不用DFS ？ 啊啊啊啊啊啊？
  因为会超时，DFS每发现一个线索都一条路走到黑，相当于把所有的可能都列出来了，然后找最小的那一个。而BFS是一层一层剥丝抽茧，最先找到的时候一定是最短的。我们来看看DFS的代码

//DFS 这方法超时~  超时，超时，超时
    int minLen = Integer.MAX_VALUE;

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        int len = wordList.size();
        int[] visited = new int[len];
        ladderLengthHelper(beginWord, endWord, visited, wordList, 0);
        return minLen == Integer.MAX_VALUE ? 0 : minLen + 1;
    }

    public void ladderLengthHelper(String word1, String endWord, int[] visited, List<String> wordList, int cnt) {
        if (word1.equals(endWord)) {
            minLen = Math.min(minLen, cnt);
            return;
        }
        int len = wordList.size();

        for (int i = 0; i < len; i++) {
            if (visited[i] == 1) {
                continue;
            }
            String word = wordList.get(i);

            if (!compareMatch(word1, word)) {
                continue;
            }
            visited[i] = 1;
            ladderLengthHelper(word, endWord, visited, wordList, cnt + 1);
            visited[i] = 0;
        }
    }

    //判断两个字符串是不是就差一个char
    public boolean compareMatch(String word1, String word2) {
        int len = word1.length();
        int cnt = 0;
        for (int i = 0; i < len; i++) {

            if (word1.charAt(i) != word2.charAt(i)) {
                cnt++;
            }

            if (cnt >= 2) {
                return false;
            }
        }
        return true;
    }