#yyds干货盘点# LeetCode程序员面试金典：单词接龙

题目：

wordlistt字典 中从单词 beginWord和 endWord 的 转换序列 根据以下规格形成的序列beginWord -> s1-> s2-> ... -> sk：

每对相邻的单词只有一个字母。

对于1 <= i <= k时，每个si都在wordList中。注意， wordList中不需要beginWord。

sk== endWord

给你两个单词 beginWord和 endWord 和一个字典 wordList ，返回 beginWord 到endWord 的 最短转换序列 中的 单词数目 。如果没有这样的转换序列，请返回 0 。

示例 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" 它不在字典中，因此不能转换。

代码实现：

class Solution {    Map<String, Integer> wordId = new HashMap<String, Integer>();    List<List<Integer>> edge = new ArrayList<List<Integer>>();    int nodeNum = 0;    public int ladderLength(String beginWord, String endWord, List<String> wordList) {        for (String word : wordList) {            addEdge(word);        }        addEdge(beginWord);        if (!wordId.containsKey(endWord)) {            return 0;        }        int[] dis = new int[nodeNum];        Arrays.fill(dis, Integer.MAX_VALUE);        int beginId = wordId.get(beginWord), endId = wordId.get(endWord);        dis[beginId] = 0;        Queue<Integer> que = new LinkedList<Integer>();        que.offer(beginId);        while (!que.isEmpty()) {            int x = que.poll();            if (x == endId) {                return dis[endId] / 2 + 1;            }            for (int it : edge.get(x)) {                if (dis[it] == Integer.MAX_VALUE) {                    dis[it] = dis[x] + 1;                    que.offer(it);                }            }        }        return 0;    }    public void addEdge(String word) {        addWord(word);        int id1 = wordId.get(word);        char[] array = word.toCharArray();        int length = array.length;        for (int i = 0; i < length; ++i) {            char tmp = array[i];            array[i] = '*';            String newWord = new String(array);            addWord(newWord);            int id2 = wordId.get(newWord);            edge.get(id1).add(id2);            edge.get(id2).add(id1);            array[i] = tmp;        }    }    public void addWord(String word) {        if (!wordId.containsKey(word)) {            wordId.put(word, nodeNum++);            edge.add(new ArrayList<Integer>());        }    }}