一个十分有趣的字符串算法题目

On April 19, 2011, in 算法, by sponge

在blogspot上看到一个十分有趣的字符串算法题目,原文在这里。作者讲述了自己面试google的一次经历。本文不理会这个故事,只来讨论一下里面着个有趣的算法。

算法题目:有两个字符串由不同的字母组成,一长一短,长的为A短的为B。设计一个算法,如果所有在B中出现的字符都在A中出现,则返回true,否则返回false。
例子:

如下字符串:

字符串A: abddfdioegdddffsfagj
字符串B: dofsjadg

字符串B中每个字符都在A中出现,返回true。

如下字符串:

字符串A: aaaabbbbbbdddddd
字符串B: acc

字符串B中有字符没在A中出现,返回false。

这只是个很基础的算法题目,相信很多人都能够立刻想出答案。

答案1:对字符串B中的每个字母在A中都遍历一遍。这个答案很烂,其时间复杂度为O(n*m)

答案2:设一个哈希表,对字符串A的字符遍历,将每个字符对应的哈希表中的值设为1。然后对B中的字符进行遍历,如果所有字符对应的hash值都为1,则返回true,否则返回false。

这个答案的时间复杂度是O(m+n),应该是大多数面试者想要的答案,相信大多数人也能想到。这样结束了?如果真结束了,那就谈不上有趣了!如果我们对空间要求比较高该怎么办

答案3:我们可以观察到,字母总共就有26个,而且在上面答案中,hash表的值只有1和0两种情况。那就好办了,我们知道int类型是32位,如果用1位(bit)来表示一个字母是否出现,那么只需1个int类型就能够表示所有的字母了。

答案3实际上跟答案2类似,换汤不换药。有趣的不是他,实际上还存在一种更有意思的方法

答案4我们为每个字母(假设字母的数量是一定的)分配一个不重复素数,比如a为2, b为3, c为5,以此类推。这样在对字符串A进行遍历时,将每个字符表示的素数相乘,最终得到一个比较大的整数。然后从字符串B中第一个字母开始,用每个字母所代表的数除这个整数,如果余数不为0,那么就返回false。如果整个遍历过程中都没有余数,则返回true。

在我第一次从原文中看到着个答案的时候,有一种眼前一亮的感觉。实际上仔细推敲,这种算法的效率并不一定比之前的答案要高,因为往往一个乘法/除法的效率要小于加减法或者比较运算。但是却给出了一种全新的考虑问题的角度,有种奇思妙想的感觉!这种方法更为巧妙,有趣!

在每个算法题目中,你在得到一个公认的比较有效的方法后,是否考虑过更简单、有趣的方法呢?

anyShare分享到:
          
Tagged with:
 

6 Responses to “一个十分有趣的字符串算法题目”

  1. dutor says:

    素数的想法确实不错,让人“眼前一亮”,但是效率肯定是没第三种算法高的,最棘手的是前26个素数的积已经是30277905337240271095741161791896580670了,用C可就麻烦了(>_<)

  2. akar says:

    ; 只有26個字母,即有 26個唯一。( 26 = 0x1A )
    ; 用 bit (位置)代表,一個 32bit 寄存器足以表達

    ;(1) 一個字母的 bit位置表示:
    and ALU 0x1F ; 結果 a=1, b=2, c=3...

    ;(2) 把 字符串 轉為 32 bit 的指紋表示,0為沒有,1為有。
    shr ; 按(1) 位移
    or ; 添加到

    ;(3) 把 字符串A 用 (2) 的代碼處理,得A的指紋
    ;(4) 把 字符串B 用 (2) 的代碼處理,得B的指紋

    ;(5) A指紋 和 B指紋比較,可得結果
    and A B
    test ALU 0

  3. shen0e says:

    其实最后一个也是一种哈希,素数表,做优化时经常用

  4. 靖难 says:

    呵呵,找26个素数是很糟糕的事情~
    当然,用数学思维去解决问题确实不错。

Leave a Reply

Note: Commenter is allowed to use '@User+blank' to automatically notify your reply to other commenter. e.g, if ABC is one of commenter of this post, then write '@ABC '(exclude ') will automatically send your comment to ABC. Using '@all ' to notify all previous commenters. Be sure that the value of User should exactly match with commenter's name (case sensitive).