Lintcode121 Word Ladder || solution 题解

【题目描述】

Given two words (startandend), and a dictionary, find all shortest transformation sequence(s) fromstarttoend, such that:

1.Only one letter can be changed at a time

2.Each intermediate word must exist in the dictionary

给出两个单词(start和end)和一个字典,找出所有从start到end的最短转换序列

比如:

1.每次只能改变一个字母。

2.变换过程中的中间单词必须在字典中出现。

【注】

·所有单词具有相同的长度。

·所有单词都只包含小写字母。

【题目链接】

www.lintcode.com/en/problem/word-ladder-ii/

【题目解析】

本题主要的框架和上一题是一样,但是还要解决两个额外的问题:

1.怎样保证求得所有的最短路径

2.怎样构造这些路径

第一问题:

不能像上一题第二点注意那样,找到一个单词相邻的单词后就立马把它从字典里删除,因为当前层还有其他单词可能和该单词是相邻的,这也是一条最短路径,比如hot->hog->dog->dig和hot->dot->dog->dig,找到hog的相邻dog后不能立马删除,因为和hog同一层的单词dot的相邻也是dog,两者均是一条最短路径。但是为了避免进入死循环,再hog、dot这一层的单词便利完成后dog还是得从字典中删除。即等到当前层所有单词遍历完后,和他们相邻且在字典中的单词要从字典中删除。 如果像上面那样没有立马删除相邻单词,就有可能把同一个单词加入bfs队列中,这样就会有很多的重复计算(比如上面例子提到的dog就会被2次加入队列)。因此我们用一个哈希表来保证加入队列中的单词不会重复,哈希表在每一层遍历完清空(代码中hashtable)。 当某一层的某个单词转换可以得到end单词时,表示已经找到一条最短路径,那么该单词的其他转换就可以跳过。并且遍历完这一层以后就可以跳出循环,因为再往下遍历,肯定会超过最短路径长度

第二个问题:

为了输出最短路径,我们就要在比bfs的过程中保存好前驱节点,比如单词hog通过一次变换可以得到hot,那么hot的前驱节点就包含hog,每个单词的前驱节点有可能不止一个,那么每个单词就需要一个数组来保存前驱节点。为了快速查找因此我们使用哈希表来保存所有单词的前驱路径,哈希表的key是单词,value是单词数组.

有了上面的前驱路径,可以从目标单词开始递归的构造所有最短路径

【参考答案】

www.jiuzhang.com/solutions/word-ladder-ii/

Like what you read? Give Cecily Lee a round of applause.

From a quick cheer to a standing ovation, clap to show how much you enjoyed this story.