一次寻找邻居单词列表的算法优化

朋友发来了一道题目进行讨论,题目的主体可以简化为如下:

定义一个单词的邻居为,与其长度相同,有且仅有一个字母不同的其他单词。对于一个单词列表,计算所有单词的邻居列表。

例如:单词sonsun为邻居,而与song不为邻居,因为它们长度不一样。

读者朋友们,看完这道题目后,请先进行独立思考,然后再展开阅读。p.s. 本文将不包含具体代码。

暴力法

第一个想法很直白,遍历所有单词,判断彼此是否为邻居,若为邻居,则将彼此加入到自己的邻居列表。

这个算法的复杂度为。n为单词的个数。当单词超过一万时,意味着有一亿次的邻居查找操作。

即使邻居判定的方法再高效,这个方法也是十分低效的。

请读者暂停阅读,思考一下如何优化。

第一次优化

根据邻居的定义,可知长度不同的单词一定不是邻居,所以对长度不同的单词的互相判断是否为邻居其实是不必要的。

可以先对单词列表进行一次预处理,将长度相同的单词放入到同一个列表中,然后对每一个这样的列表内进行彼此邻居的判定。

假设所有单词的长度可以均分为10份,则每一个列表的长度可约等n/10,整个的复杂度为,虽然还是,但是已经比之前的暴力法要高效好几倍。

已经考虑到这一步的同学请再次暂停,思考有无数量级上提升的解决方案。

第二次优化

由于第一次优化并没有将实质性的复杂度降低,所以在单词很多的情况下还是比较低效。

我们需要重新审题,看能不能发现一点什么。

了解正则表达式的同学都知道,s.n这个匹配可以匹配son,也可以匹配sun。也就是说s.nsonsun的共同匹配。而.un则是sungun的共同匹配。

邻居单词之间都有某种联系,这种联系就是它们都有一个共同的匹配。所以,我们可以遍历所有单词,建立以匹配为,匹配的单词列表为的字典,然后遍历每个匹配的单词列表,这些单词列表中的所有单词都互相为对方的邻居单词。

例如:

  1. 当遍历到单词sun时,sun有三个匹配,[.un, s.n, su.]。匹配字典中将加入这几个匹配,这时候字典的内容为{ .un=>[sun], s.n=>[sun], su.=>[sun] }
  2. 当遍历到单词son时,son有三个匹配,[.on, s.n, so.]。匹配字典中将加入这几个匹配,这时候字典的内容为{ .un=>[sun], s.n=>[sun, son], su.=>[sun], .on=>[son], so.=>[son] }。其中,sonsun共同的匹配s.n对应的列表加入了son
  3. 当遍历到单词gun时,gun有三个匹配,[.un, g.n, gu.]。匹配字典中将加入这几个匹配,这时候字典的内容为{ .un=>[sun, gun], s.n=>[sun, son], su.=>[sun], .on=>[son], so.=>[son], g.n=>[gun], gu.=>[gun] }。其中,sungun共同的匹配.un对应的列表加入了gun

对于每一个单词,假设单词的长度为L,则单词有L个匹配。对于n个单词,则最多有n*L个匹配列表。假设最长的匹配列表的长度为m,则整个算法的复杂度为。由于每个单词的邻居不会太多,所以基本可以将m视为常数。所以整个算法的复杂度为

如果当单词列表长度n远大于最长单词的长度L时,这个算法的复杂度将为,线性时间。

回顾

不知道有多少同学看过《编程珠玑》。这本书的第二章有一个aha moment,表示忽然习得的灵感。

其中本文的最后一个算法与第二章的变位词算法有相似之处。都是基于标识(索引)来解决问题。

而解决问题的关键在于发现问题可以用标识来解决,即邻居间的共性是存在一个共同的匹配,而每个单词的匹配都是有限的(跟单词的长度一致)。

6 responses

  1. 典型的空间换时间,以冗余换取效率。题目本身很有代表性,赞一个!

  2. 不知道你有没有考虑这n*L个匹配进行排序的时候时间算了没呢?每次把新的匹配加入到字典中都是需要全部比较的,排序时间复杂度呢

    • 额。。好久之前的题目了。。
      首先,是不需要排序的,因为只需要按照键插入至以索引为键的字典就行了,这个操作是O(1)的复杂度。然后求每个单词的邻居列表的话,也是可以把邻居列表设为字典,遍历一遍之前索引的字典,将其加入就行了,从头到尾好像没遇到任何排序的内容
      其次,因为m和l相对于n来说极小,所以可以认为是常数,整个时间复杂度还是线性的,我记得经过测试对比把圣经,双城记等书所有单词输入,原来算法2需要耗时1分多钟的操作可以降低到1-2秒完成

  3. 补充一下,在正则表达式中 ‘?’ 表示匹配零次或一次,s?n 匹配的是 {sn,n},正确的表达式应该是 s[a-z]n 或者简略点的 s.n 。

    • 嗯,这个我知道,当时写的时候问号看起来比较显眼就用了问号,赞细心

发表评论

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