【題目描述】
Given two words (startandend), and a dictionary, find all shortest transformation sequence(s) 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)。
【注】
·所有單詞具有相同的長度奄侠。
·所有單詞都只包含小寫字母。
【題目鏈接】
www.lintcode.com/en/problem/word-ladder-ii/
【題目解析】
本題主要的框架和上一題是一樣，但是還要解決兩個(gè)額外的問題：
1.怎樣保證求得所有的最短路徑
2.怎樣構(gòu)造這些路徑
第一問題：
不能像上一題第二點(diǎn)注意那樣，找到一個(gè)單詞相鄰的單詞后就立馬把它從字典里刪除撩满，因?yàn)楫?dāng)前層還有其他單詞可能和該單詞是相鄰的，這也是一條最短路徑绅你，比如hot->hog->dog->dig和hot->dot->dog->dig伺帘，找到hog的相鄰dog后不能立馬刪除，因?yàn)楹蚳og同一層的單詞dot的相鄰也是dog忌锯，兩者均是一條最短路徑伪嫁。但是為了避免進(jìn)入死循環(huán)，再hog汉规、dot這一層的單詞便利完成后dog還是得從字典中刪除礼殊。即等到當(dāng)前層所有單詞遍歷完后，和他們相鄰且在字典中的單詞要從字典中刪除针史。 如果像上面那樣沒有立馬刪除相鄰單詞晶伦，就有可能把同一個(gè)單詞加入bfs隊(duì)列中，這樣就會(huì)有很多的重復(fù)計(jì)算（比如上面例子提到的dog就會(huì)被2次加入隊(duì)列）啄枕。因此我們用一個(gè)哈希表來保證加入隊(duì)列中的單詞不會(huì)重復(fù)婚陪，哈希表在每一層遍歷完清空（代碼中hashtable）。 當(dāng)某一層的某個(gè)單詞轉(zhuǎn)換可以得到end單詞時(shí)频祝，表示已經(jīng)找到一條最短路徑泌参，那么該單詞的其他轉(zhuǎn)換就可以跳過。并且遍歷完這一層以后就可以跳出循環(huán)常空，因?yàn)樵偻卤闅v沽一，肯定會(huì)超過最短路徑長度
第二個(gè)問題：
為了輸出最短路徑，我們就要在比bfs的過程中保存好前驅(qū)節(jié)點(diǎn)漓糙，比如單詞hog通過一次變換可以得到hot铣缠，那么hot的前驅(qū)節(jié)點(diǎn)就包含hog，每個(gè)單詞的前驅(qū)節(jié)點(diǎn)有可能不止一個(gè)，那么每個(gè)單詞就需要一個(gè)數(shù)組來保存前驅(qū)節(jié)點(diǎn)蝗蛙。為了快速查找因此我們使用哈希表來保存所有單詞的前驅(qū)路徑蝇庭，哈希表的key是單詞，value是單詞數(shù)組.
有了上面的前驅(qū)路徑捡硅，可以從目標(biāo)單詞開始遞歸的構(gòu)造所有最短路徑
【參考答案】
