天天看点

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.通过广搜 计算出终结点到各个节点的最短距离(包括源节点到终结点的最短距离,也就是和 最短转换序列的长度对应)

继续阅读