首页 > 代码库 > 判断一个字符串的所有字符是否都在另一个字符串中
判断一个字符串的所有字符是否都在另一个字符串中
网上流传了一个故事,说是在google面试的故事,故事中说最后一道面试题就是假设有两个字符串,一个长一些(字符串1),一个短一些(字符串2),如何判断这个短字符串中的每个字符是否都在这个长字符串中。假设每个字符串都是由26个小写字母组成的。
最后这个大牛提到了用一个素数代表一个字母,把字符串1的字母的积(当然会很大)算出来,然后除以字符串2的每个字符代表的素数。如果每个字符代表的素数都能被整除,说明字符串2中的每个字符都在字符串1中。时间复杂度为O(n+m)
这确实是一个巧妙的方法,不过实现起来却不是很容易。这里针对这个特殊的要求,可以用位图或者hash的思路来解决。
无论是字符串1还是字符串2,都是由【a-z】字母组成的,所以最多只有26个字母,所以只要一个整数(32位)就可以表示字符串所表示的字母,假设这个字母出现,则对应的位置1,那么就算26个字母都出现了,也只需要26位置1.则该思路的c++实现代码如下:
bool is_contained(const char* str1,const char* str2) { int strmap = 0; const char * pstr = str1; while(*pstr != '\0') { strmap |= ( 1 << (*pstr - 'a')); pstr++; } pstr = str2; bool iscontained = true; while(*pstr != '\0') { if((strmap & (1 << (*pstr - 'a'))) == 0) { iscontained = false; break; } pstr++; } return iscontained; }
判断一个字符串的所有字符是否都在另一个字符串中
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。