兄弟单词查询

一个单词单词字母交换，可得另一个单词，如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;  
}

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