给定两个单词（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" 不在字典中，所以无法进行转换。思路： （主要解释来自参考2）
先附一下二叉树的BFS/层序遍历模板。
public List<List<Integer>> BFS(TreeNode root) { List<List<Integer>> allResults = new ArrayList<>(); if (root == null) return allResults; Queue<TreeNode> nodes = new LinkedList<>(); nodes.add(root); while (!nodes.isEmpty()) { int levelSize = nodes.size(); List<Integer> results = new ArrayList<>(); for (int i = 0; i < levelSize; i++) { TreeNode currNode = nodes.poll(); results.add(currNode.val); if (currNode.left != null) nodes.add(currNode.left); if (currNode.right != null) nodes.add(currNode.right); } allResults.add(results); } return allResults; }过程：
无向图中两个顶点之间的最短路径的长度，可以通过广度优先遍历得到；
为什么 BFS 得到的路径最短？
可以把起点和终点所在的路径拉直来看，两点之间线段最短。（想象层层水波往外辐射）
可能过程如下图：
由于代码是从a-z循环替换判断，所以实际替换过程走上半段，即 "hit" -> "hot" -> "dot" -> "dog" -> "cog" 。
代码：
class Solution { public int ladderLength(String beginWord, String endWord, List<String> wordList) { Queue<String> q = new LinkedList<>(); q.offer(beginWord); HashSet<String> wordSet = new HashSet<>(wordList); wordSet.remove(beginWord); // the same as marking visited int step = 1; while (!q.isEmpty()) { int size = q.size(); while (size-- > 0) { String str = q.poll(); if (str.equals(endWord)) return step; // found shortest transformation path for (int i = 0; i < str.length(); i++) { char[] chars = str.toCharArray(); for (char c = 'a'; c <= 'z'; c++) { // try to change 1 character of `str` chars[i] = c; String newStr = new String(chars); if (wordSet.contains(newStr)) { q.offer(newStr); wordSet.remove(newStr); // the same as marking visited } } } } step++; } return 0; // no such transformation sequence. } }时间复杂度： O ( 26 ∗ M ∗ N ) O(26*M*N) O(26∗M∗N)，M是单词长度，N是输入字典表长度。(待确认) 空间复杂度： O ( M ∗ N ) O(M*N) O(M∗N) (待确认)
思路：
已知目标顶点（即终点），可从分别起点和终点执行BFS，直到遍历有交集，这种方式搜索的单词数量会更小点。而且每次可以从单词数量少的集合开始扩散，以提升速度。
这里 start(visited) 和 end(visited) 交替使用，等价于单向 BFS 里使用队列，每次扩散都要加到总的 visited 里。
代码：
class Solution { public int ladderLength(String beginWord, String endWord, List<String> wordList) { Set<String> dict = new HashSet<>(wordList); Set<String> start = new HashSet<>(); Set<String> end = new HashSet<>(); Set<String> visited = new HashSet<>(); // 1. initialize the beginWord start.add(beginWord); // 2. all transformed words must be in dict (including endWord) if (dict.contains(endWord)) end.add(endWord); // 3. BFS for (int len = 2; !start.isEmpty(); len++) { Set<String> current = new HashSet<>(); for (String w : start) { for (int j = 0; j < w.length(); j++) { char[] ch = w.toCharArray(); for (char c = 'a'; c <= 'z'; c++) { if (c == w.charAt(j)) continue; // beginWord and endWord not the same, so bypass itself ch[j] = c; String nb = String.valueOf(ch); if (end.contains(nb)) return len; // meet from two ends if (dict.contains(nb) && visited.add(nb)) current.add(nb); // not meet yet, visited is safe to use } } } start = (current.size() < end.size()) ? current : end; // switch to small one to traverse from other end end = (start == current) ? end : current; } return 0; } }时间复杂度： O ( 26 ∗ M ∗ N ) O(26*M*N) O(26∗M∗N)，M是单词长度，N是输入字典表长度。 空间复杂度： O ( M ∗ N ) O(M*N) O(M∗N)
1、单词接龙 2、广度优先遍历、双向广度优先遍历（Java） 3、[Java] BFS Solution - Clean code 4、Simple Java BFS solution with explanation 5、Two-end BFS in Java 31ms.
