Word Ladder

一个单词字典，里面有一系列很相似的单词，然后给了一个起始单词和一个结束单词，每次变换只能改变一个单词，并且中间过程的单词都必须是单词字典中的单词，让我们求出最短的变化序列的长度。
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.

这题有个很明显的特征，就是需要考虑到26个字母组合的问题，用上面的例子说明，hit如何变化，
1.从第一个h开始变，可以有ait,bit,cit,dit......然后判断中间态的单词是否在wordList中，发现没有，再从第二个i开始变，发现hot中间态在wordList中，此时不要终止，得继续走完hia，hib，hic.....
2.对于hot重复上述操作，从第一个开始变，aot,bot,cot,dot.......发现dot在wordList，
3.重复1，2的过程中，如果刚好发现单词变成了cog,那我们的目的达到了

类似上述的变化，就像一个BFS，广度优先遍历的过程。hit，分别将三个单词找到所有的可能性，也就是它的下一层，再分别对下一层进行继续BFS，既然说到了BFS，那么就需要有一个队列，这个队列用来保存每一次的中间态，比如最开始只有hit,后来有了hot，后来有了dot......

**问题：如果不用a到z遍历，类似于hit单词在wordList里面找，发现有一个字母跟它不一样的，就暂存作为中间态。此时继续将这个中间态的单词再重复来，没试过这个方法

• php

 /**
     * @param String $beginWord
     * @param String $endWord
     * @param String[] $wordList
     * @return Integer
     */
    function ladderLength($beginWord, $endWord, $wordList) {
        if (!in_array($endWord, $wordList)) {
            return 0;
        }
        $pathCnt = [
            $beginWord => 1,
        ];
        $queue   = new splqueue();
        $queue->enqueue($beginWord);
        while (!$queue->isEmpty()) {
            $word = $queue->dequeue();
            for ($i = 0; $i < strlen($word); $i++) {
                $newWord = $word;
                for ($ch = ord("a"); $ch <= ord("z"); $ch++) {
                    $str = chr($ch);
                    $newWord[$i] = $str;
                    if (in_array($newWord, $wordList) && $newWord == $endWord) {
                        return $pathCnt[$word] + 1;
                    }

                    if (in_array($newWord, $wordList) && !array_key_exists($newWord, $pathCnt)) {
                        $queue->push($newWord);
                        $pathCnt[$newWord] = $pathCnt[$word] + 1;
                    }
                }
            }
        }
        return 0;
    }

• java 方法，对于过程，表格详细描述

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;
    }

• 一种较为简洁的解法，原理还是BFS

 public int ladderLength3(String beginWord, String endWord, List<String> wordList) {
        HashSet<String> set = new HashSet<String>(wordList);
        Queue<String> queue = new LinkedList<String>();
        queue.offer(beginWord);
        int res = 0;
        while (!queue.isEmpty()) {

            // 一层一层来
            for (int k = queue.size(); k > 0; k--) {
                String word = queue.poll();
                if (word.equals(endWord)) {
                    return res + 1;
                }
                for (int i = 0; i < word.length(); i++) {
                    char[] charArray = word.toCharArray();
                    for (char ch = 'a'; ch <= 'z'; ch++) {

                        charArray[i] = ch;
                        String newString = new String(charArray);
                        // 变化后的word在set中，但是还未到终点
                        if (set.contains(newString) && newString != word) {
                            queue.offer(newString);
                            set.remove(newString);
                        }
                    }
                }
            }
            res++;
        }
        return 0;
    }