Anagrams 变位词

本文要讨论的是变位词，也就是说通过交换一个单词的各个字母的顺序能变成另一个单词，那么这两个单词互为变位词。
 
问题一：判断给定的两个单词（标准ASCII）是否变位词
 
方法一：用两个数组分别统计两个字符串里每个字符出现的个数，如果完全一致，则是变位词，否则不是.
 
这个方法是大小写敏感的。这个方法能支持的输入字符串的最大长度 将受 用来统计字符个数的数组的类型 的限制。如果用unsigned char[128]来统计字符个数，unsigned char最大值是255(0xFF)，那么能支持的输入字符串最大长度是255。对于长度大于255的字符串将有可能出现误判。比如分别由256个"a"和256个"b"组成的两个字符串，统计结果都是全0，程序将误判为是变位词。如果改为用unsigned int[128]，则能支持的输入字符串的最大长度是0xFFFFFFFF。但占用的内存是前者的4倍。
 
另外，下面的实现中将统计结果数组定义为static。理由一，不在调用栈上，可以避免在占用有限的stack空间，理由二，也没有在堆上，避免该函数被频繁调用的时候会产生大量的空间申请和释放的操作。（这两个理由成立吗？充分吗？）
 
[cpp]  
bool IsAnagram1(const char *pStr1, const char *pStr2)  
{  
    static int stat1[128] = {0};  
    static int stat2[128] = {0};  
      
    memset(stat1, 0, sizeof(stat1));  
    memset(stat2, 0, sizeof(stat1));  
      
    const char *p = pStr1;  
    while (*p != '\0') {  
        stat1[*p]++;  
        p++;  
    }  
    p = pStr2;  
    while (*p != '\0') {  
        stat2[*p]++;  
        p++;  
    }  
    return (0 == memcmp(stat1, stat2, sizeof(stat1)));  
}  
 
方法二：利用这个原理：两个素数集合所含的素数和每个素数的个数都相等 当且仅当 每个集合所有元素的乘积相等。所以，令每个字符对应一个素数，分别计算每个字符串中所有字符所对应的素数的乘积。如果两个乘积相等，则是变位词。这个方易做图受到数据最大值的限制。假设输入字符仅包含a-z的26个字符(大小写不敏感)，则为了区分这26个字符，需要用到26个素数（2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101）分别对应a到z。最大值是101。另外我们需要一个足够大的数据类型来正确保存素数乘积，double型最大值为1.79769e+308。如果输入字符全部为对应素数101的那个字符z，那么最多可以支持153个。101^153小于DBL_MAX，101^154大于DBL_MAX。也就是说如果某个字符串含有154个z，那么素数乘积将越界，结果无法判断。
[cpp] 
bool IsAnagram2(const char *pStr1, const char *pStr2)  
{  
    static const int PrimeNumber[26] = {2, 3, 5, 7, 11, 13, 17, 19, 23,  
                                        29, 31, 37, 41, 43, 47, 53, 59,  
                                        61, 67, 71, 73, 79, 83, 89, 97, 101};  
    double f1 = 1.0;  
    const char *pa = pStr1;  
    while (*pa != '\0') {  
        if (*pa >='A' && *pa <='Z')  
            f1 *= PrimeNumber[*pa + ('a'-'A') - 'a'];  
        else  
            f1 *= PrimeNumber[*pa - 'a'];  
        pa++;  
    }  
    double f2 = 1.0;  
    const char *pb = pStr2;  
    while (*pb != '\0') {  
        f2 *= PrimeNumber[*pb - 'a'];  
        pb++;  
    }  
    return f1 == f2;  
}  
对方法二的一种可能的改进是借用其他能够支持大数计算的Lib来完成素数的乘积。本文不再给出代码。
 
另一种改进可以将字符分组，分别判断两个字符串所含每一组字符是否一致。两个字符串是变位词 当且仅当 字符串所含每一组字符所对应的素数的乘积都分别相等。这样，可以增加能够判断的字符串的长度和字符范围。比如按大小写分组，即可实现26*2种不同字符组成的字符串的变位词判断，支持最大字符长度153（下面的代码给出了这个实现）。或者仍然不区分大小写，将26个字母分为a-m和n-z两组，每组13个字符，用到前13个素数，第13个素数是41，double最大值可以表示41的最高次方是191次方。即可实现26种不同字符组成的字符串的变位词判断，支持最大字符长度191。
 
[cpp]  
bool IsAnagram3(const char *pStr1, const char *pStr2)  
{  
    static const int PrimeNumber[26] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29,  
                                        31, 37, 41, 43, 47, 53, 59, 61, 67,  
                                        71, 73, 79, 83, 89, 97, 101};  
    double fUpcase1 = 1.0;  
    double fLowCase1 = 1.0;  
    const char *p = pStr1;  
    while (*p != '\0') {  
        if (*p >='A' && *p <='Z')  
            fUpcase1 *= PrimeNumber[*p -'A'];  
        else  
            fLowCase1 *= PrimeNumber[*p - 'a'];  
        p++;  
    }  
      
    double fUpcase2 = 1.0;  
    double fLowCase2 = 1.0;  
    p = pStr2;  
    while (*p != '\0') {  
        if (*p >='A' && *p <='Z')  
            fUpcase2 *= PrimeNumber[*p -'A'];  
        else  
            fLowCase2 *= PrimeNumber[*p - 'a'];  
        p++;  
    }  
      
    return (fLowCase1 == fLowCase2) && (fUpcase1 == fUpcase2);  
}

补充：软件开发 , C++ ,