天天看點

lintcode 單詞接龍II

  給出兩個單詞(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.通過廣搜 計算出終結點到各個節點的最短距離(包括源節點到終結點的最短距離,也就是和 最短轉換序列的長度對應)

繼續閱讀