最近总是Rank到很难的题目,这次遇到了LeetCode中通过率最低的题目。这道题目是一个图相关的问题,同时牵扯到很多坑,很多细节,即使思路正确稍不注意内存超出,时间超出都是常事儿,自己做出来还是需要废一番功夫的。博主写了BFS算法的大概就放弃了,后面翻了几份代码,找了个最简洁的 ,这里也只能讲解一下别人的代码了。

题目

Given two words (beginWord and endWord), and a dictionary’s word list, find all shortest transformation sequence(s) from beginWord toendWord, such that:

  1. Only one letter can be changed at a time
  2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]

Return

[ [“hit”,”hot”,”dot”,”dog”,”cog”], [“hit”,”hot”,”lot”,”log”,”cog”] ]

Note:

  • Return an empty list 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.

UPDATE (2017/1/20):
The wordList parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

分析

这里直接看代码吧,基本思路就是转化为一个图搜索问题,下面只介绍几个坑:

1. 因为要寻找所有的最短路径,设置visited、finished的时候,要在一层都处理完之后再设置,如上图,b和a同时可以到达d点,使用传统dfs就会少一条路径。

2. 使用邻接链表来处理连接点,这个连接是单向的,这是为了避免后面DFS找到更远的路径

3. 通过BFS来记录连接,后面通过DFS来恢复路径

其它地方都在代码里面写了注释

代码

注释版本,后面还有未带注释的版本,看着简洁舒服很多

不带注释版本的代码:

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注