這道題思路不難，本質就是BFS嘛，從一個單詞開始，他的下一層是所有可以一步變到，且從來沒變到過得那些string。問題是怎樣確定這些可以變到的string呢？有兩個條件，一，只能通過上一層的string變化一個數字得到，二，變化之後單詞必須在字典中。注意是變化一個字母得到，而不是編輯距離是1，要麼就復雜了，情況多了好多好多。
我最開始的思路是建個map，保存所有從開始單詞能變化到得單詞及這些單詞一步能變化到的那些單詞。too young too simple, 在一個字典非常大的測試用例上超時了。為什麼會超時呢，因為字典很大的時候，大家都能互相變來變去，生成我這個映射後的字典代價很大，因為每次都要驗證這個單詞跟它後面的所有單詞是不是只相差了一個字符，建成了這個映射字典，以後每次還是要在map中查找。
那怎麼辦？還有一個看似不起眼，其實很關鍵的條件沒有使用，那就是所有的單詞的長度都一樣！還好英文字母一共26個，而且在set的和map中查找的速度都很快，而且，單詞長度都還相同，那麼我們就從頭開始嘗試，每次變換一位，看看變化之後的是不是要求的？如果不是，看看在不在字典中，在字典中且沒訪問過加入到下一層中。嘗試完這一波後，把剛變化的位置恢復，這樣保證了每次只有一位不一樣。有那麼點暴力卻行得通。
ac代碼：
class Solution {
public:
int ladderLength(string start, string end, unordered_set &dict) {
if(start == end)
return 2;
if(dict.size()<=0)
return 0;
queue que;
set visited;
int res = 2, len = start.length();
que.push(start);
que.push("");
bool flag = false;
string tps(start);
char tp;
while(!que.empty()){
tps = que.front();
que.pop();
if(tps == ""){
if(que.empty()){
return 0;
}else{
res++;
que.push("");
continue;
}
}
for(int i=0;i
