在图中进行广度优先遍历（BFS），进而寻找最短的路径。
例：LeetCode 第 279 题：完全平方式
传送门：279. 完全平方数。
给定正整数 n，找到若干个完全平方数（比如
1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。示例 1:
输入: n = 12 输出: 3 解释: 12 = 4 + 4 + 4.示例 2:
输入: n = 13 输出: 2 解释: 13 = 4 + 9.
Python 代码：
练习：LeetCode 第 127 题：单词接龙
传送门：127. 单词接龙。
给定两个单词（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" 不在字典中，所以无法进行转换。
分析：这道题目可以建模成一个有向图，原问题就可以抽象成一个有向无权图的最短路径问题，可以称之为套路的解决方案就是“广度优先遍历（BFS）”，明白了这些以后，写出正确的代码就不是难事。
注意：（1）“图”的广度优先遍历使用的辅助数据结构有两个，一个是队列（用于一层一层排队），一个是一个数组或者是集合（用于判断当前考虑的元素是否以前已经处理过）。
回顾：如果是树结构的广度优先遍历，就无需设置辅助的数组或者集合用于判断以前是否处理过。
其实，只要思路很清楚，写出 AC 解就是自然而然的事情了。这里我说的自然而然是相比较于要考虑很多特殊情况（边界情况，+1或者 -1 情况）的简单问题来说，这道问题应该划分到简单。毕竟广度优先遍历是一个常规问题，不需要使用到什么小技巧。
下面谈一谈我在解题过程中的一些优化：
（1）原来是遍历 wordList，看看目标 word 与它们只差一个字母的情况，此时在 wordList 很大的情况下效率低下，故将 wordList 改成 HashSet，利用 HashSet 查询高效性避免了去遍历这件事情；
（2）char[] 数组这件事情，其实还可以用 StringBuilder。（3）考虑能不能使用 Trie。
<script src="https://gist.github.com/liweiwei1419/8e7e0d3914e103c1d3ba4634033c9c9c.js"></script>
Python 代码：
练习：LeetCode 第 126 题：单词接龙 II
传送门：126. 单词接龙 II。
给定两个单词（beginWord 和 endWord）和一个字典 wordList，找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则：
- 每次转换只能改变一个字母。
- 转换过程中的中间单词必须是字典中的单词。
说明:
- 如果不存在这样的转换序列，返回一个空列表。
- 所有单词具有相同的长度。
- 所有单词只由小写字母组成。
- 字典中不存在重复的单词。
- 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
示例 1:
输入: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] 输出: [ ["hit","hot","dot","dog","cog"], ["hit","hot","lot","log","cog"] ]示例 2:
输入: beginWord = "hit" endWord = "cog" wordList = ["hot","dot","dog","lot","log"] 输出: [] 解释: endWord "cog" 不在字典中，所以不存在符合要求的转换序列。
分析：很遗憾，我自己只写出了超时解。不过思路至少还是对的。先使用广度优先搜索得到最短层数，再使用深度优先搜索得到所有的最短路径。
Python 代码：
（本节完）
