CareerCup之1.4判斷字符串是否為變位詞

由於組成變位詞的字符是一模一樣的， 因此我們可以先統計每個字符串中各個字符出現的次數， 然後看這兩個字符串中各字符出現次數是否一樣。如果是，則它們是一對變位詞。 這需要開一個輔助數組來保存各字符的出現次數。我們可以開一個大小是256的整數數組， 遍曆第一個字符串時，將相應字符出現的次數加1；遍曆第二個字符串時， 將相應字符出現的次數減1。最後如果數組中256個數都為0，說明兩個字符串是一對變位詞。 (第1個字符串中出現的字符都被第2個字符串出現的字符抵消了)， 如果數組中有一個不為0，說明它們不是一對變位詞。

/*********************************
*   日期：2014-05-06
*   作者：SJF0115
*   題目: 判斷字符串是否為變位詞
*   來源：CareerCup
**********************************/
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;

//判斷字符串是否為變位詞
bool IsAnagrams(string str1,string str2){
    if(str1 == "" || str2 == ""){
        return false;
    }
    int len1 = str1.length();
    int len2 = str2.length();
    //變位詞長度一樣
    if(len1 != len2){
        return false;
    }
    //排序
    sort(&str1[0],&str1[0]+len1);
    sort(&str2[0],&str2[0]+len2);
    if(str1 == str2){
        return true;
    }
    else{
        return false;
    }
}

int main(){
    char str1[] = "the eyes";
    char str2[] = "they see";
    bool result = IsAnagrams(str1,str2);
    cout<<result<<endl;
    return 0;
}

//判斷字符串是否為變位詞
bool IsAnagrams(string str1,string str2){
    int i;
    if(str1 == "" || str2 == ""){
        return false;
    }
    int len1 = str1.length();
    int len2 = str2.length();
    //變位詞長度一樣
    if(len1 != len2){
        return false;
    }
    //初始化
    int vis[256];
    memset(vis,0,sizeof(vis));
    //遍曆第一個字符串，將相應字符出現的次數加1
    //遍曆第二個字符串，將相應字符出現的次數減1
    for(i = 0;i < len1;i++){
        vis[str1[i]] ++;
        vis[str2[i]] --;
    }
    //判斷是否為變位詞 如果數組中256個數都為0，說明兩個字符串是一對變位詞。
    for(i = 0;i < 256;i++){
        if(vis[i] != 0){
            return false;
        }
    }
    return true;
}