兄弟單詞查詢

一個單詞單詞字母交換，可得另一個單詞，如army->mary，成為兄弟單詞。提供一個單詞，在字典中找到它的兄弟。描述數據結構和查詢過程。   分析：網上對這個問題有好多解法。我用計數排序的方法來解決這個問題。任何一個單詞（假設都是小寫）中的一個字母的ASCII碼值的范圍為97-（97+26）。兄弟單詞的字母都是一樣的，只是順序不同。我們設兩個數組比如A[26],B[26]，遍歷單詞中的字母。單詞的字母ASCII碼設為變量i，兄弟單詞的字母的ASCII碼設為變量j，然後，A[i-97]++,B[j-97]++。最後遍歷單詞的字母，遍歷變量設為i，若對於所有的i，A[i-97]==B[i-97]，則這兩個單詞為兄弟單詞。通過這樣的方法，可以得到算法復雜度為O(n)的算法。   代碼：    

bool IsBrotherWords(const std::string &str1,const std::string &str2)  
{  
    int nLength1=str1.length();  
  
    int  nLength2=str2.length();  
  
    //長度不等肯定不是兄弟單詞  
    if(nLength1!=nLength2)  
        return false;  
  
    //設兩個數組  
    int a[26],b[26];  
  
    //初始化  
    for(int i=0;i<26;++i)  
    {  
        a[i]=b[i]=0;  
    }  
  
    //對單詞中的字母開始計數  
    for(int i=0;i<nLength1;++i)  
    {  
        a[str1.at(i)-97]++;  
        b[str2.at(i)-97]++;  
    }  
  
    //判斷計數是否一樣，若不一樣這不是兄弟單詞  
    for(int i=0;i<nLength1;i++)  
    {  
        if(a[str1.at(i)-97]!=b[str1.at(i)-97])  
            return false;  
  
    }  
  
    return true;  
  
}  

 

    可以對上面的代碼進行優化，使用一個數組，對單詞的每個字母計數加1，對兄弟單詞的每個字母計數減一。若最後這個數組的計數都是0，則這兩個單詞為兄弟單詞。    

bool IsBrotherWords2(const std::string &str1,const std::string &str2)  
{  
    int nLength1=str1.length();  
  
    int  nLength2=str2.length();  
  
    //長度不等肯定不是兄弟單詞  
    if(nLength1!=nLength2)  
        return false;  
  
    //設計數數組  
    int a[26];  
  
    for(int i=0;i<26;++i)  
    {  
        a[i]=0;  
    }  
  
    //開始計數  
    for(int i=0;i<nLength1;++i)  
    {  
        a[str1.at(i)-97]++;  
        a[str2.at(i)-97]--;  
    }  
  
    //如果最後計數不為0，則不為兄弟單詞  
    for(int i=0;i<nLength1;i++)  
    {  
        if(a[str1.at(i)-97]!=0)  
            return false;  
  
    }  
  
    return true;  
  
}  

 

  算法時間復雜度為O（2*Length+26），Length為單詞的長度。   測試代碼：    

int _tmain(int argc, _TCHAR* argv[])  
{  
  
    std::string str1("army");  
    std::string str2("mary");  
  
bool b= IsBrotherWords(str1,str2);  
bool b2=IsBrotherWords2(str1,str2);  
  
     return 0;  
}