一个关于字符串匹配的算法题目

有这样一个算法题目

假设这有一个各种字母组成的字符串,假设这还有另外一个字符串,而且这个字符串里的字母数相对少一些。从算法是讲,

什么方法能最快的查出所有短字符串里的字母在长字符串里都有?

比如,如果是下面两个字符串:

 

String 1: ABCDEFGHLMNOPQRS

String 2: DCGSRQPOM

答案是true,所有在string2里的字母string1也都有。如果是下面两个字符串:

 

String 1: ABCDEFGHLMNOPQRS

String 2: DCGSRQPOZ

答案是false,因为第二个字符串里的Z字母不在第一个字符串里。

 

立刻能想到的就是遍历了,然后进一步思考得到以后的几种方法,

方法一;将短字符串中每个字符在长字符串中遍历,时间复杂度为O(m*n)

 

方法二;设置一个哈希表,对长字符串的字符遍历,将每个字符对应的哈希表中的值设为1。然后对短字符进行遍历,

如果所有字符对应的哈希值都为1,则返回true,否则返回false。这样时间复杂度就是O(m+n).

 

方法三;我们可以观察到,字母总共就有26个,hash表的值只有1和0两种情况,我们知道int类型是32位,如果用1位(bit)来表示一个字母是否出现,

那么只需1个int类型就能够表示所有的字母了。将长字符串中每个字符的哈希值在相应的位中设为1,短字符串遍历同方法二。

 

方法四;是比较独特奇妙的,我们为每个字母(假设字母的数量是一定的)分配一个不重复素数,比如a为2, b为3, c为5,以此类推。

这样在对字符串A进行遍历时,将每个字符表示的素数相乘,最终得到一个比较大的整数。然后从字符串B中第一个字母开始,

 

用每个字母所代表的数除这个整数,如果余数不为0,那么就返回false。如果整个遍历过程中都没有余数,则返回true。

第四种方法给人眼前一亮的感觉,比较新颖奇特,效率也不一定比第三种优,但是这启发我们在学习算法的时候多去从多方面考虑,同时也要打好数学基础。

 

 


这个面试题来自一个有趣的故事,原故事参加http://www.vaikan.com/google-interviewing-story/

原文地址:https://www.cnblogs.com/coderchuanyu/p/3841601.html