九章算法面试题41 判断单词的包含关系
浏览数：43 /
时间：2015年06月08日
九章算法官网-原文网址
http://www.jiuzhang.com/problem/41/
题目
给定两个单词A和B（假设均为小写字母，并且不含重复字母），判断A是否包含B。这里所定义的包含，只需要包含所有的字母即可，不要字母之间的顺序和邻接关系。要求想出尽可能多的方法（不限制复杂度）
解答
方法1：枚举法。对于单词A，枚举每个字母，看是否在B中出现，时间复杂度O(nm)，空间复杂度O(1)。
方法2：哈希表。将A中字母序列转换为字母集合，判断B中每个字母是否在集合中。该集合的结构则是用哈希表实现。时间复杂度O(n+m)，空间复杂度O(26)
方法3：二进制。可以用位运算替代方法2中的哈希表，用4字节整数的每一个二进制位代表某个字母是否出现过。时间复杂度O(n+m)，空间复杂度O(1)
方法4：素数积。将a,b,c,d,e.. 对应到整数序列的若干素数2,3,5,7,11 …那么每个单词均可以用若干素数的乘积来代表。计算出A和B分别所对应的乘积，判断是否整除即可。时间复杂度O(n+m)，空间复杂度O(26)，缺点是需要高精度运算支持。
面试官角度
方法包含但不限于上述四种。这个题目本身是十分简单的，难点在于你能想到多少种可行办法。考察的是求职者的思维是否活跃。上述的方法各有优劣。同时面试官也可能会跟面试者讨论，如果不限制在小写字母，不限制字符是否重复，算法该做如何的变化？
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
