在圖中進行廣度優(yōu)先遍歷（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 的最短轉換序列的長度睦番。轉換需遵循如下規(guī)則：
- 每次轉換只能改變一個字母。
- 轉換過程中的中間單詞必須是字典中的單詞耍属。
說明:
- 如果不存在這樣的轉換序列托嚣，返回 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" 不在字典中，所以無法進行轉換舍咖。
分析：這道題目可以建模成一個有向圖矩父，原問題就可以抽象成一個有向無權圖的最短路徑問題，可以稱之為套路的解決方案就是“廣度優(yōu)先遍歷（BFS）”排霉，明白了這些以后窍株，寫出正確的代碼就不是難事。
注意：（1）“圖”的廣度優(yōu)先遍歷使用的輔助數據結構有兩個攻柠，一個是隊列（用于一層一層排隊）球订，一個是一個數組或者是集合（用于判斷當前考慮的元素是否以前已經處理過）。
回顧：如果是樹結構的廣度優(yōu)先遍歷瑰钮，就無需設置輔助的數組或者集合用于判斷以前是否處理過冒滩。
其實，只要思路很清楚浪谴，寫出 AC 解就是自然而然的事情了开睡。這里我說的自然而然是相比較于要考慮很多特殊情況（邊界情況，+1或者 -1 情況）的簡單問題來說较店，這道問題應該劃分到簡單士八。畢竟廣度優(yōu)先遍歷是一個常規(guī)問題，不需要使用到什么小技巧梁呈。
下面談一談我在解題過程中的一些優(yōu)化：
（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 的最短轉換序列。轉換需遵循如下規(guī)則：
- 每次轉換只能改變一個字母叫挟。
- 轉換過程中的中間單詞必須是字典中的單詞艰匙。
說明:
- 如果不存在這樣的轉換序列，返回一個空列表抹恳。
- 所有單詞具有相同的長度员凝。
- 所有單詞只由小寫字母組成。
- 字典中不存在重復的單詞奋献。
- 你可以假設 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" 不在字典中，所以不存在符合要求的轉換序列糖埋。
分析：很遺憾宣吱，我自己只寫出了超時解。不過思路至少還是對的阶捆。先使用廣度優(yōu)先搜索得到最短層數凌节，再使用深度優(yōu)先搜索得到所有的最短路徑。
Python 代碼：
（本節(jié)完）
