127. 单词接龙 (opens new window)

1.BFS广度优先遍历

分析：从起始/终止单词开始搜索，BFS在广搜时遍历过的节点呈辐射状，需要使用数据结构保存每一层的所有元素。注意区分按层深搜和广搜的区别。这里从终止单词开始广搜，整体思路如下：

• 遍历每一层的节点，对于每个元素从队列中出队。如果当前元素就是起始元素，说明找到了最短路径，当前搜索树的层数就是转换序列的长度。
• 找出剩余单词表当中，如果可以被“当前元素”转换：
  • 说明该单词位于“当前元素”下一层，将该单词加入到队尾。
  • 同时从单词表删掉该单词(相当于访问位的作用)

除此之外，还有一些细节可优化的地方：

• 为了保证起始节点在树中能够被广搜到，需要将起始单词加入到单词表。
• 使用for外面的变量来控制List索引，从而在遍历同时删掉list中的元素。

对于BFS而言还有另外一种写法，相当于层序遍历不断循环遍历队列，上一层的所有节点一定先于下一层被搜索到。层数(树高)可以在外围用一个map保存，或者用一个for进行控制。

class Solution {
    Map<String, Integer> cache = new HashMap<>();
    int res=0;
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if(wordList.contains(endWord)) wordList.remove(endWord);
        else return 0;
        //起始元素加入列表当中
        wordList.add(beginWord);
        Deque<String> deque = new LinkedList<>();
        deque.offerLast(endWord);
        bfs(wordList,deque,beginWord,1);
        return res;
    }
    //广搜
    public void bfs(List<String> wordList,Deque<String> deque,String beginWord,int layer){
        int size = deque.size();
        if(size==0) return;
        for(int i=0;i<size;i++){
            String s = deque.pollFirst();
            if(s.equals(beginWord)){
                res = layer;
                return;
            }
            int wordSize = wordList.size();
            //小技巧：遍历list的同时删掉容器中的元素
            int inx=0;
            for(int k=0;k<wordSize;k++){
                if (check(wordList.get(inx), s)) {
                    deque.offerLast(wordList.get(inx));
                    wordList.remove(inx);
                }
                else inx++;
            }
        }
        bfs(wordList, deque, beginWord, layer + 1);
    }
    public boolean check(String s, String t) {
        int num = 0;
        for (int i = 0; i < s.length(); i++) if (s.charAt(i) != t.charAt(i)) num++;
        if (num != 1) return false;
        return true;
    }
}