給出兩個單詞(start和end)和一個字典,找出所有從start到end的最短轉換序列
比如:
1、每次隻能改變一個字母。
2、變換過程中的中間單詞必須在字典中出現。
所有單詞具有相同的長度。
所有單詞都隻包含小寫字母。
給出資料如下:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
傳回
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
根據每兩個單詞是否隻差一個字母,進行建圖,然後如下。
1.深搜 + 回溯 + 記憶化(記錄每個節點到 終結點 的最短轉換序列),逾時啦。。。
2.通過廣搜 計算出終結點到各個節點的最短距離(包括源節點到終結點的最短距離,也就是和 最短轉換序列的長度對應)