腾讯的一道面试题，欢迎讨论

Charistain_huang 2011-01-10 05:04:01

假设两个字符串中所含有的字符和个数都相同我们就叫这两个字符串匹配，比如：abcda和adabc,由于出现的字符个数都是相同，只是顺序不同，所以这两个字符串是匹配的。。要求高效
现在需要你来实现下面的函数：
boolen Is_Mach(char *str1,char *str2)

大家来讨论讨论吧，我觉得这个比较有意思，电子词典中就存在相似的问题。。
我想了好久也只想到一些基本的方法，效率也不高，还请大家来晒晒自己的方法吧？？？

...全文

4641 238 打赏收藏转发到动态举报

写回复

用AI写文章

238 条回复

切换为时间正序

请发表友善的回复…

发表回复

qingtianweichong 2012-09-06

打赏
举报

学习中！位图刚听说！

淮安老丁 2012-09-06

打赏
举报

觉得这方法挺好的，但觉得是不是先比较一下长度，，然后在比较删除。假如两个字符串都很很长，比较了半天，发现长度不匹配，这样效率是不是很低，但对于短的字符串就无所谓了。
小小见解，望指导
[Quote=引用 1 楼的回复:]
没想到什么好方法，
遍历一次，删除一个字符，
如此至字符串长度，或者是不相等。
[/Quote]

SillyBenzhu 2012-09-05

打赏
举报

[Quote=引用 19 楼的回复:]

引用 14 楼 jexbow 的回复:

分别对两个字符串求检验和，同时记录字符个数，如果最后的校验和相等，且字符个数相等的话那就是一样的了。

int is_match(char* str1, char* str2)
{
char c1 = '\0';
char c2 = '\0';
int n1 = 0, n2 = 0;

while('\0' != *str1)
……
[/Quote]
char a[] = "1258";
char b[] = "1168";
就会认为是match的！

PIE 2012-09-04

打赏
举报

遍历字符串，用两个int或double数字统计加权和：len1 +=*p1 - 'm' len2 +=*p2 - 'm'
同时统计字符个数。

陈思有 2012-09-03

打赏
举报

#include <stdio.h>

#include <string.h>



#define STRLEN 100

#define ASCIILEN 128



void main()

{

	char str1[STRLEN], str2[STRLEN];

	int str1Sum = 0, str2Sum = 0;   //用来存放两个字符串所含字符的个数

	int str1Count[ASCIILEN] = { 0 }, str2Count[ASCIILEN] = { 0 };  //用来计算各个字符的个数

	int i = 0;  //计数

	int sum = 0;  



	printf("输入字符串1\n");

	scanf("%s",str1);

	printf("输入字符串2\n");

	scanf("%s",str2);

	

	str1Sum = strlen(str1);

	str2Sum = strlen(str2);



	if (str1Sum != str2Sum)

	{

		printf("两个字符串不相同\n");

	}

	else

	{

		for (i = 0; i < str1Sum; ++i)

		{

			str1Count[str1[i]]++;

		}



		for (i = 0; i < str2Sum; ++i)

		{

			str2Count[str2[i]]++;

		}



		for (i = 0; i < ASCIILEN; ++i)

		{

			if (str1Count[i] != str2Count[i])

			{

				break;

			}

			sum += str1Count[i];

			if (sum == str1Sum)

			{

				break;

			}

		}



		if (i == ASCIILEN || sum == str1Sum)

		{

			printf("两个字符串相同\n");

		}

		else

		{

			printf("两个字符串不同\n");

		}

	}

}

xxb249 2012-09-03

打赏
举报

呵呵有一个特别简单的方法：
假设 char src1[] = "abcdefdjaidjadjapodjasojfidofhdsufhdshfdshgufdghufdghudfghudhgid";
char src2[] = "japodjasojfidofhdsuabcdefdjaidjadfhdshfhufdghudfgdshgufdghudhgid";
int sumStr1 = 0;
int sumStr2 = 0;

第一步：大家都这样写
if (strlen(src1) != strlen(src2))
return 0;
第二步：分别计算src1 和 src2 的数组中相对应的accii码值

for（int ii = 0； ii < 数组个数；ii++）
sumStr1 += src1[ii];

for（int ii = 0； ii < 数组个数；ii++）
sumStr2 += src2[ii];

if (sumStr1 == sumStr2)
{
printf("匹配")；
}
else

{
printf("不匹配")；
}

GameOver

无知者无谓 2012-09-03

打赏
举报

如果不考虑多字节文字，分别统计2个字符串中字符出现次数，在用统计进行比较会比较好一些，复杂度O(m+n+127)

bright0923 2012-09-02

打赏
举报

[Quote=引用 4 楼的回复:]

C/C++ code
bool Is_Mach(char *str1,char *str2)
{
const int MAX = 255;

int histogram1[MAX];
int histogram2[MAX];
memset(histogram1, 0, MAX);
memset(histogram2, 0, MAX);

int ……
[/Quote]
+++

MaGic_VV311 2012-09-02

打赏
举报



bool Is_Match(char *pStr1,char *pStr2)

{

    int sdwCount=0;

    char aList[256]={0};

    int aArray[256]={0};

    char *pTemp=NULL;

    

    for(pTemp=pStr1;*pTemp!='\0';pTemp++)

    {

        aArray[(WORD32)*pTemp]++;

        aList[sdwCount++]=*pTemp;        

    }



    for(pTemp=pStr2;*pTemp!='\0';pTemp++)

    {

        aArray[(WORD32)*(pTemp)]--;

        if(aArray[*pTemp]<0)

        {

            return false;

        }        

    }

    

    while(sdwCount-->=0)

    {

        if(aArray[(WORD32)aList[sdwCount]]!=0)

        {

            return false;

        }

    }

    return true;

};

发了3次。。。
1 数组清0，str1 Hash 增值
2 str2 Hash 减值，若值为负，直接判为false
3 检查最终相关数值是否为0

MaGic_VV311 2012-09-02

打赏
举报

bool Is_Match(char *pStr1,char *pStr2)
{
int sdwCount=0;
char aList[256]={0};
int aArray[256]={0};
char *pTemp=NULL;

for(pTemp=pStr1;*pTemp!='\0';pTemp++)
{
aArray[(WORD32)*pTemp]++;
aList[sdwCount++]=*pTemp;
}

for(pTemp=pStr2;*pTemp!='\0';pTemp++)
{
aArray[(WORD32)*(pTemp)]--;
if(aArray[*pTemp]<0)
{
return false;
}
}

while(sdwCount-->=0)
{
if(aArray[(WORD32)aList[sdwCount]]!=0)
{
return false;
}
}
return true;
};

MaGic_VV311 2012-09-02

打赏
举报

itachi0 2011-10-16

打赏
举报

开两个数组，int A[256], int B[256], 这两个数组分别用来记录两个字符串中的各字符出现次数，最后比较两个数组就行了，如果完全一样，就是相同的

lezai001 2011-10-03

打赏
举报

各种大神……

xz0404 2011-10-03

打赏
举报

209楼才是正确答案。
其他都是太有空了想太多。

正在无聊中 2011-10-03

打赏
举报



#include<iostream>

#include<cstring>

using namespace std;

bool Is_Match(char *str1,char *str2)

{

 if(strlen(str1)!=strlen*str2)return false;

 else

 {

  int i,j;

  for(i=0;i<strlen(str1);i++)

   for(j=i+1;j<strlen(str1);j++)

    if(str1[i]>str1[j])

    {

     char tmp;

     tmp=str1[i];

     str1[i]=str1[j];

     str1[j]=tmp;

    }

  for(i=0;i<strlen(str2);i++)

   for(j=i+1;j<strlen(str2);j++)

    if(str2[i]>str2[j])

    {

     char tmp;

     tmp=str2[i];

     str2[i]=str2[j];

     str2[j]=tmp;

    }

  return !strcmp(str1,str2);

 }

}

int main()

{

 char str1[100],str2[1000];

 cin >> str1 >> str2;

 cout << "YesOrNo:" << Is_Match(str1,str2) << endl;

 return 0;

}

正在无聊中 2011-10-03

打赏
举报



#include<iostream>

#include<cstring>

using namespace std;

bool Is_Match(char *str1,char *str2)

{

 if(strlen(str1)!=strlen*str2)return false;

 else

 {

  int i,j;

  for(i=0;i<strlen(str1);i++)

   for(j=i+1;j<strlen(str1);j++)

    if(str1[i]>str1[j])

    {

     char tmp;

     tmp=str1[i];

     str1[i]=str1[j];

     str1[j]=tmp;

    }

  for(i=0;i<strlen(str2);i++)

   for(j=i+1;j<strlen(str2);j++)

    if(str2[i]>str2[j])

    {

     char tmp;

     tmp=str2[i];

     str2[i]=str2[j];

     str2[j]=tmp;

    }

  return !strcmp(str1,str2);

 }

}

int main()

{

 char str1[100],str2[1000];

 cin >> str1 >> str2;

 cout << "YesOrNo:" << Is_Match(str1,str2) << endl;

 return 0;

}

wolaiye_1_3 2011-09-28

打赏
举报



int Is_Mach(char *str1, char *str2)

{

  int i=0,j;

  while(1)

  {

    if('\0' == str1[i])

      return 1;

    j=0;

    while(1)

    {

      if('\0' == str2[j])

        return 0;

      if(str1[i] == str2[j])

      {

        str2[j] = 0xff;

        break;

      }

      j++;

    }

    i++;

  }

}