【題目描述】
Given two words (startandend), and a dictionary, find the length of shortest transformation sequence fromstarttoend, such that:
1.Only one letter can be changed at a time
2.Each intermediate word must exist in the dictionary
給出兩個(gè)單詞（start和end）和一個(gè)字典葵姥，找到從start到end的最短轉(zhuǎn)換序列
比如：
1.每次只能改變一個(gè)字母尿孔。
2.變換過程中的中間單詞必須在字典中出現(xiàn)咨跌。
【注】1、如果沒有轉(zhuǎn)換序列則返回0誓琼。
2、所有單詞具有相同的長度。
3晦闰、所有單詞都只包含小寫字母。
【題目鏈接】
www.lintcode.com/en/problem/word-ladder/
【題目解析】
這道題是套用BFS同時(shí)也利用BFS能尋找最短路徑的特性來解決問題鳍怨。
把每個(gè)單詞作為一個(gè)node進(jìn)行BFS呻右。當(dāng)取得當(dāng)前字符串時(shí)，對(duì)他的每一位字符進(jìn)行從a~z的替換鞋喇，如果在字典里面声滥，就入隊(duì)，并將下層count++侦香，并且為了避免環(huán)路落塑，需把在字典里檢測到的單詞從字典里刪除。這樣對(duì)于當(dāng)前字符串的每一位字符安裝a~z替換后罐韩，在queue中的單詞就作為下一層需要遍歷的單詞了憾赁。
正因?yàn)锽FS能夠把一層所有可能性都遍歷了，所以就保證了一旦找到一個(gè)單詞equals（end）散吵，那么return的路徑肯定是最短的龙考。
【參考答案】
