【腾讯】报纸与信件的字符匹配效率问题

题目：有一个江洋大盗，他每次写信都是从一张报纸上剪下单词，再把单词贴在信上。假如某张报纸的单词保存在vector<string>paper 中，而信的单词保存在vector<string>letter 中，写一个算法程序判别该报纸可不可以生成该信？

 

对比一些方法： 这里假设paper:(m个单词，每个单词平均d个字母),letter:(n个单词，每个单词平均d个字母)。对于中文词语而言，一般2~4个字左右，对于英文单词，d就要大一点，但基本上也是常数。因此d远远小于m，下面比较的时候就不考虑单词中每个字符间的比较了。


(1) 蛮力匹配：
    把n中每个单词与m中的每个单词一一比较。时间复杂度为：O(m*n)。估计谁也不会选这种。

(2) 二分查找：要求，对paper建有序索引。
    paper排序的时间复杂度最好为O(m*logm)。
    对letter中的所有单词二分查找的时间复杂度为O(n*logm)
    总的时间复杂度为O((m+n)*logm). 比蛮力查找效率要好不少。

    缺点：如果换了新报纸，所有的单词都必须重新排序，需要O(m*logm)的时间来建立索引。

(3) trie树： 要求，对paper建trie索引树

    paper建立trie树的时间复杂度为O(m)。
    对letter中所有单词在trie树中查找的时间复杂度为O(n).
    总的时间复杂度为O(m+n)。效率绝对要比二分查找好。

    优势: 如果换了新报纸，重新建立一颗trie树的时间O(m)也小于二分查找建立有序索引的时间O(m*logm)要小的多。

    缺点：建立trie树所需要的空间代价是很大的。如果是中文词语的trie树，那么放进全部加载进内存是很可怕的，需要把trie树用B树的方法存储在磁盘上。详见：《Trie树 》

(4) Hash表： 要求，对paper建立Hash结构

    建立Hash表结构的时间复杂度为O(m)，注意需要计算每个单词的HashCode的时候，很可能要遍历单词中的每个字母。
    对letter中所有单词在Hash结构中查找的时间复杂度为O(n)。当然，这是在没有任何散列冲突的理想情况下。选择好HashCode的计算方式和散列表的大小，可以将冲突降到很低。因此我们这里不考虑冲突。
    总的时间复杂度为O(m+n)。由此可见，Hash表结构与Trie树的效率都是相当的客观。

    缺点：如果换报纸。为了考虑冲突的可能性，Hash结构的大小可能需要重新考虑。这一点很麻烦。当然，存储空间上应该会比Trie要好一些，但实际应用上并不比Trie方便。


(5) 归并查找：要求，对letter和paper都建立有序索引。

    对letter和paper排序的时间复杂度分别为O(m*logm)和O(n*logn)
    归并查找的时间复杂度为O(m+n)
    总的时间复杂度为O(m*logm+n*logn+m+n)

总结：对于这几种方法而言，我更加青睐于trie树。因为我相信报纸中的单词数量基本上是保持稳定的，不可能达到海量级别。Trie树的空间代价其实并不算什么。

 

评论

1 楼 blackdog1987 2012-08-16  

还看到过一个理论上的方法，不过很好玩
首先我们知道 素数是无穷多的

那么，每个单词标记一个素数
A中的所有素数相乘   得到X
B中的所有素数相乘   得到Y
若X%Y == 0
表示可以生成（素数只能整除1和他本身）
否则 不能生成

缺陷很明显，如果单词很多的话，素数的乘积会非常的大，而且求模非常的慢（当然求模也是可以进行优化的，这里不赘述）