单词接龙

题目

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

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

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

解题思路

初看完全没有思路，细品后才觉得有一定树状关系：A单词有n个相关单词（只有一个字母不同），n个相关单词中又会衍生出n*m个相关单词，然后继续衍生....
知道是树形关系之后，题目要求的是最短转换长度，转换题意就是求树中两个单词的最短路径。
那么接下来就好说了，最短路径通常采用广度搜索，借用一个队列的情况下，广度搜索的复杂度为O(n)，加上生成关系数的复杂度O(n)（遍历wordList得出每个通配词和其对应的单词列表的HashMap）。

• 注：通配词的意思为只有一个字母不同的单词串，比如 hit 的通配词有it，ht，hi三个，题目中通配词do对应的数组为：[‘dot’，‘dog’]。

上图.jpg

代码

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        // 生成通用单词表，用哈希表存储
        HashMap<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
        for (String str : wordList) {
            for (int i = 0; i < str.length(); i++) {
                String newString = str.substring(0, i) + '*' + str.substring(i + 1, str.length());
                ArrayList<String> list = map.get(newString);
                if (list == null) {
                    list = new ArrayList<String>();
                    map.put(newString, list);
                }
                list.add(str);
            }
        }
        return findWord(beginWord, endWord,map);
    }
    public int findWord (String beginWord, String endWord,HashMap<String, ArrayList<String>> map){
        // 1. 创建队列，利用先进先出特性，BFS遍历n叉树
            Queue<Pair<String, Integer>> Q = new LinkedList<Pair<String, Integer>>();
            Q.add(new Pair(beginWord, 1));
            HashMap<String, Boolean> visited = new HashMap<String, Boolean>();
            visited.put(beginWord, true);
            while (!Q.isEmpty()) {
            Pair<String, Integer> node = Q.remove();
            String word = node.getKey();
            int level = node.getValue();
            for (int i = 0; i < word.length(); i++) {
        // 2. 生成单词的的通配词，再从对应的map表中遍历对应的数组。
                String newWord = word.substring(0, i) + '*' + word.substring(i + 1, word.length());
                for (String adjacentWord : map.getOrDefault(newWord, new ArrayList<String>())) {
        // 3. 从数组中匹配endWord。
                if (adjacentWord.equals(endWord)) {
                    return level + 1;
                }
        // 4. 为了避免重复单词在队列中造成死循环，需要visited数组记录是否被访问过
                if (!visited.containsKey(adjacentWord)) {
                    visited.put(adjacentWord, true);
                    Q.add(new Pair(adjacentWord, level + 1));
                }
                }
            }
            }
            return 0;
    }
}

总结

1. 本题囊括了好几个知识点，树的概念，队列，广度优先搜索，哈希表，层级遍历模板，访问性数组...前天才刚了解了广度优先的遍历套路，确实用的还不太熟练。五遍刷题法根本没做到（其实还是因为没有时间）
2. java还是不熟悉，边查边学边用真是效率太低。泛型用的真是头疼，一个数组八种实现，真TM要命。
3. 不能再拿笔记本刷了，一屏看13行代码，逻辑翻来翻去真是要砸桌子了，下周无论如何把显示器搬回来。
4. 一下午死磕了一道题，有成有败，需要赶紧再刷几道类似的找找自信。
5. 听说还有双向广度优先遍历，就是从开始出发寻找的同时，从尾部用相同逻辑向前查找，应该还会节约一些时间.....很厉害的样子，等tm复习时候再优化。