**一. 題目描述** Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that: ? Only one letter can be changed at a time? ? Each intermediate word must exist in the dictionary For example, Given: start = “hit”? end = “cog”? dict = [“hot”,”dot”,”dog”,”lot”,”log”] As one shortest transformation is ”hit” -> ”hot” -> ”dot” -> ”dog” -> ”cog”, return its length 5. Note: ? Return 0 if there is no such transformation sequence.? ? All words have the same length.? ? All words contain only lowercase alphabetic characters. **二. 題目分析** 參考鏈接：[http://www.mamicode.com/info-detail-448603.html](http://www.mamicode.com/info-detail-448603.html) 可以將這道題看成是一個圖的問題。我們將題目映射到圖中，頂點是每個字符串，然后兩個字符串如果相差一個字符則進行連邊。我們的字符集只有小寫字母，而且字符串的長度固定，假設是L。那么可以注意到每一個字符可以對應的邊有25個（26個小寫字母去掉自己），那么一個字符串可能存在的邊是25*L條。接下來就是檢查這些對應的字符串是否在字典內，就可以得到一個完整的圖的結構。根據題目要求，等價于求這個圖中一個頂點到另一個頂點的最短路徑，我們一般用BFS廣度優先。 這道題，我們只能用最簡單的辦法去做，每次改變單詞的一個字母，然后逐漸搜索，這種求最短路徑，樹最小深度問題用BFS最合適。 和當前單詞相鄰的單詞，就是和頂點共邊的另一個頂點，是對當前單詞改變一個字母且在字典內存在的單詞。 找到一個單詞的相鄰單詞，加入BFS隊列后，我們要從字典內刪除，因為不刪除會造成類似hog->hot->hog這樣的死循環。而且刪除對求最短路徑沒有影響，因為我們第一次找到的單詞肯定是最短路徑，我們是層序遍歷去搜索的，最早找到的一定是最短路徑，即使后面的其他單詞也能轉換成它，路徑肯定不會比當前的路徑短。這道題僅要求求出最短路徑長度，不需要求輸出最短路徑，所以可以刪除這個單詞。 BFS隊列之間用空串”“來標示層與層的間隔，每次碰到層的結尾，遍歷深度+1，進入下一層。 **三. 示例代碼** ~~~ class Solution { public: int ladderLength(string start, string end, unordered_set<string> &dict) { if(start.size() == 0 || end.size() == 0) return 0; queue<string> wordQ; wordQ.push(start); wordQ.push(""); int path = 1; while(!wordQ.empty()) { string str = wordQ.front(); wordQ.pop(); if(str != "") { int len = str.size(); for(int i = 0; i < len; i++) { char tmp = str[i]; for(char c = 'a'; c <= 'z'; c++) { if(c == tmp) continue; str[i] = c; if(str == end) return path + 1; //如果改變后的單詞等于end 返回path+1 if(dict.find(str) != dict.end()) { wordQ.push(str); dict.erase(str); //字典內刪除這個詞 防止反復走 } } str[i] = tmp; //重置回原來的單詞 } } else if(!wordQ.empty()) { //到達當前層的結尾，并且不是最后一層的結尾 path++; wordQ.push(""); } } return 0; } }; ~~~