关于传说中的皮裤Guy的面试题

2016-09-03 本文已影响38人 Kent_Zhang

我似乎找到了一个O(m+n)的算法，同样简洁但是没有数字相乘造成太大数字的风险，无论多长的两个字符串，都只需要消耗一个8个字节的额外内存用于计算。

简单的说就是运用位运算，由于大小写字母总共有52个，所以可用一个长整型64位，每一位代表其中某一个字母。先遍历短字符串，对位掩码进行位设置操作，比如存在a则设置最低位为1。

然后遍历长字符串，对每个字母所代表的位进行清0，比如存在a则设置最低位为0。

遍历过后，如果64位长整型仍然非0，则证明短字符串不是长字符串的子集。

以上，叙述比较简单抽象…………实在是没精神多写啊………………