120. Word Ladder

Description

Given two words (start and end), and a dictionary, find the shortest transformation sequence from start to end, output the length of the sequence.

Transformation rule such that:

Only one letter can be changed at a time

Each intermediate word must exist in the dictionary. (Start and end words do not need to appear in the dictionary )

Return 0 if there is no such transformation sequence.

All words have the same length.

All words contain only lowercase alphabetic characters.

You may assume no duplicates in the word list.

You may assume beginWord and endWord are non-empty and are not the same.

Example

Example 1:

Input:start = "a",end = "c",dict =["a","b","c"]

Output:2

Explanation:

"a"->"c"

Example 2:

Input:start ="hit",end = "cog",dict =["hot","dot","dog","lot","log"]

Output:5

Explanation:

"hit"->"hot"->"dot"->"dog"->"cog"

思路:

类似于发现一个拓扑排序,起点是start,终点是end,但是不同于一般的拓扑排序,并没有给图的信息,此题需要自己用BFS构建一个有向图,要注意不能出现双向箭头,并且一个层级的点之间没有箭头。一直遍历到出现end点结束。

刚开始写了个比较方法去比较dict中点与点之间是否满足变换条件,然后每次循环调用,最后会导致超时(下图中是反面例子),借鉴答案用26个字母先得到每个单词的变换集合再去dict中查找会比较有效率。


代码:


©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • rljs by sennchi Timeline of History Part One The Cognitiv...
    sennchi阅读 7,486评论 0 10
  • pyspark.sql模块 模块上下文 Spark SQL和DataFrames的重要类: pyspark.sql...
    mpro阅读 9,539评论 0 13
  • 近几天学习python学得头昏脑涨 , 回顾一下, 又感受不到自己真的学到了什么. 故意识到了养成博客做记录的重要...
    兰舟的地球一跳阅读 98评论 0 0
  • 尽管我们都听说过刻意练习,尽管我们知道想要做什么都需要不停地练习,但是实际之中我们用的时候却是少之又少。 我们知道...
    我是狐狸一只阅读 160评论 0 5
  • “我们那个年代奶都喷出来,很多很多,现在的年轻人都没奶。”“宝宝哭了就是没吃饱,泡奶粉!”当越来越多的妈妈“被没奶...
    等等麻米阅读 763评论 0 2