127. 单词接龙

和433.最小基因变化这道题一样的解法。
https://blog.csdn.net/qq_43606119/article/details/135538247

class Solution {public int ladderLength(String beginWord, String endWord, List<String> wordList) {Set<String> cnt = new HashSet<>();for (int i = 0; i < wordList.size(); ++i) {cnt.add(wordList.get(i));}if (!cnt.contains(endWord)) return 0;Set<String> visited = new HashSet<>();Queue<String> q = new ArrayDeque<>();q.offer(beginWord);visited.add(beginWord);int step = 1;while (!q.isEmpty()) {int size = q.size();for (int i = 0; i < size; ++i) {String curr = q.poll();for (int u = 0; u < curr.length(); ++u) {for (int v = 0; v < 26; ++v) {if (curr.charAt(u) != 'a' + v) {StringBuffer sb = new StringBuffer(curr);sb.setCharAt(u, (char)('a' + v));String next = sb.toString();if (!visited.contains(next) && cnt.contains(next)) {if (next.equals(endWord)) return step + 1;q.offer(next);visited.add(next);}}}}}++step;}return 0;}
}

改进：

在本题中可以使用虚拟节点将各个单词进行连接，例如hit可以有三个虚拟节点hi*、h*t、*it，将其和hit进行连接，所有单词都如此处理，优化建图。

注意因为添加了虚拟节点，所以我们得到的距离为实际最短路径长度的两倍。同时我们并未计算起点对答案的贡献，所以我们应当返回距离的一半再加一的结果。

class Solution {Map<String, Integer> wordID = new HashMap<>();List<List<Integer>> edge = new ArrayList<>();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;}// 初始化dis数组，表示从beginWord到每个单词的最短转变路径长度，初始值为Integer.MAX_VALUE。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> q = new LinkedList<>();q.offer(beginID);while (!q.isEmpty()) {int curr = q.poll();if (curr == endID) return dis[curr] / 2 + 1;for (int e : edge.get(curr)) {if (dis[e] == Integer.MAX_VALUE) {dis[e] = dis[curr] + 1;q.offer(e);}}}return 0;}private void addEdge(String word) {addWord(word);int id1 = wordID.get(word);char[] array = word.toCharArray();for (int i = 0; i < array.length; ++i) {char temp = 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] = temp;}}private void addWord(String word) {if (!wordID.containsKey(word)) {wordID.put(word, nodeNum++);edge.add(new ArrayList<Integer>());}}
}