腾讯面试题假设两个字符串中所含有的字符和个数都相同我们就叫这两个字符串匹配,比如:abcda和adabc,由于出现的字符个数都是相同,只是顺序不同,所以这两个字符串是匹配的.要求高效现在
来源:学生作业帮助网 编辑:六六作业网 时间:2024/12/19 23:28:12
腾讯面试题假设两个字符串中所含有的字符和个数都相同我们就叫这两个字符串匹配,比如:abcda和adabc,由于出现的字符个数都是相同,只是顺序不同,所以这两个字符串是匹配的.要求高效现在
腾讯面试题
假设两个字符串中所含有的字符和个数都相同我们就叫这两个字符串匹配,比如:abcda和adabc,由于出现的字符个数都是相同,只是顺序不同,所以这两个字符串是匹配的.要求高效
现在需要你来实现下面的函数:
boolen Is_Mach(char *str1,char *str2)
有人给出的代码如下,vc6.0上编译
#include
#define true 1
#define false 0
typedef int boolean;
boolean Is_Mach(char *str1,char *str2) {
int cnt[256] = {0}, i;
char *p1 = str1, *p2 = str2;
if ( p1 == p2 )
return true;
if ( p1 == NULL || p2 == NULL )
return false;
while ( *p1 && *p2 )
cnt[ *p1++ ]++, cnt[ *p2++ ]--;
if ( *p1 != *p2 )
return false;
for ( i=0; i
腾讯面试题假设两个字符串中所含有的字符和个数都相同我们就叫这两个字符串匹配,比如:abcda和adabc,由于出现的字符个数都是相同,只是顺序不同,所以这两个字符串是匹配的.要求高效现在
这个算法利用计数已经达到O(n)的时间复杂度了,只对两个输入做了一遍扫描.空间复杂度也有所改进,从两个数组减少为一个数组,提前判断也做了,我想象不到还有什么算法能够更快.
只是数组256这里有点小问题.使用数组256表示作者希望能对0x80之后的字符进行计数,但这句话“cnt[ *p1++ ]++”有问题:*p1如果大于0x80,那么它是一个负数,这会造成错误的元素被计数,应该加个unsigned char做下限定.