单词接龙问题

| Comments

昨天看到其他部门的技能鉴定题目,相对我们部门偏应用的题目,他们的相对更加偏重算法。题目描述如下:

有一种单词接龙的游戏,就是连续的两个单词,第一个单词的尾要和第二个单词的头是一样的。
例如: cat tell log google就是一个单词接龙。

定义最少单词接龙是单词个数最少的接龙,定义最短单词接龙是单词字母个数总和最少的接龙。 假设所有单词都是由小写字母组成,现在给定一堆单词,给定龙头和龙尾,求出最少单词接龙和最短单词接龙。

当时在招聘,一时也没反应过来。下午回来的时候,仔细一想,这不就是最短路径问题么?

把26个小写字母看成是结点,那么每个单词就是从某个结点到另外一个结点的单向路径。
上面的接龙如果在加上单词gc, cookie,就是下面的图表示:
单词接龙

最少单词接龙,就是每条路径的权值为1,求两个结点之间的最短路径。
最短单词接龙,就是每条路径的权值为单词的长度,求两个结点之间的最短路径。

另外,关于一些特殊情况和注意点:

对于存在多个单词,他们的首尾字母相同的话,只记录长度最短的为路径的权值即可。

结点的存储可以不用链接表,因为只有26个字母,用二维数组即可,实时增加单词也容易处理。

求最短路径的算法,参考经典的Dijkstra最短路径算法,这里就不详述了。 关于Dijkstra,可以参考百度百科中的条目

Comments