本文要討論的是變位詞，也就是說通過交換一個單詞的各個字母的順序能變成另一個單詞，那麼這兩個單詞互為變位詞。 問題一：判斷給定的兩個單詞（標准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); }
