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


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

分别统计一下两个字符串里各个字母出现多少次，然后比较次数就行

好想法。

先排序，再用函数库中的一个比较两个字符串是否相同的那个strcmp（）

/*
根据楼主的一个简单实现。只做了字母与数字的匹配，读者可以根据你的需要加以更改，如有疑问可以QQ:153612021
愿大家共同进步。

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

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <malloc.h>

#define MAX_INT 40


int stat(char *str1,int *data)
{
    int i;
    int temp;
    int length;

    if(str1==NULL ||data==NULL)
    {
        printf("point is NULL");
        return -1;
    }
   
    length =strlen(str1);
    for(i =0;i<length;i++)
    {
        if(isdigit(temp=*str1))
        {
            data[temp-'0']++;
        }else{
            if(isupper(temp)){           
                data[temp-'A'+10]++;
            }else{
                data[temp-'a'+10]++;
            }   
        }
        str1++;
    }
   
    for(i =0;i<MAX_INT;i++){
        printf("%d\t",data[i]);
    }
    printf("\n---------------\n");
    return 0;



}


int is_Mach(char *str1,char *str2){

    int a[MAX_INT]={0};
    int b[MAX_INT]={0};


    printf("str1:%s\nstr2:%s\n",str1,str2);
   

    if(strlen(str1)!=strlen(str2)){
        printf("length is not the same\n");
        return -1;
    }
    if(stat(str1,a)==-1 ||stat(str2,b)==-1)
    {
        printf("stat is error");
        return -1;
    }

    for(int i =0;i<MAX_INT;i++)
    {
        if(a[i]!=b[i])
            return -1;
    }
   

    return 0;
}


void main(int argc,char **argv)
{
    char *str1,*str2;
    char *str3 ="abcdefg";
    char *str4 ="bcdefag";

    if(  ((str1=(char*)malloc(sizeof(100*sizeof(char))))==NULL) ||
        ((str1=(char*)malloc(sizeof(100*sizeof(char))))==NULL) )
    {
        printf("malloc is error");

    }

    if(argc==3){
        str1=argv[1];
        str2=argv[2];

        if(is_Mach(str1,str2)==0){
            printf("match\n");
        }else{
            printf("no match\n");
        }
    }else{
        if(is_Mach(str3,str4)==0){
            printf("match\n");
        }else{
            printf("no match\n");
        }
    }



}

[ 本帖最后由 gavinsurekam 于 2011-1-10 18:21 编辑 ]

四楼的方法不错　

楼上的，所有的 ，效率 太低了。

我可以做到 O(m+n)的效率。

直接 xor 看最后的结果是不是0.

真可惜，这种做法有不低的机率是错的，就是说这种做法只能判断不匹配，而不能判断匹配

#include<iostream>
#include<cassert>
#include<cstring>
bool is_Match(const char * str1 , const char * str2)
{
    assert( NULL != str1 && NULL != str2);
    if ( strlen( str1) != strlen( str2 ) )
    {
        return false;
    }
    int ret = static_cast<int>(str1[0]);
    for ( int i=1 ; str1[i] != '\0' ; i ++)
    {
        ret ^= static_cast<int>(str1[i]);
    }
    for ( int i = 0; str2[i] != '\0' ; i ++)
    {
        ret ^= static_cast<int>(str2[i]);
    }
    return ret == 0 ? true:false;
}

int main()
{
    const char *str1 = "abc";
    const char *str2 = "cba";
    if (! is_Match(str1,str2) )
    {
        std::cout<<"Do not Matches"<<std::endl;
    }
    return 0;
}

[ 本帖最后由 Devil_W 于 2011-1-10 19:26 编辑 ]

哎，原来是一个自以为是的家伙。。。无语了

    const char *str1 = "abcaa";
    const char *str2 = "cba";
拿去试

或者
    const char *str1 = "abcaa";
    const char *str2 = "cbabb";

随便你