比较两个字符串是否为变位词

(1) 问题描述：如果两个字符串的字符一样，但是顺序不一样，被认为是兄弟字符串，问如何在迅速匹配兄弟字符串（如，bad和adb就是兄弟字符串）。

(2) 注意：第一点中讨论了字符串包含问题，但是不要以为两个字符串互相包含就是（变位词）兄弟字符串了，例如aabcde和edcba互相包含，但它们不是变位词。

(3) 解决方案：

• 思路一

  给每个字母分配一个素数，可以通过判断两个字符串的素数乘积是否相等。跟上述素数法一样，时间复杂度也是O(n+m)，需要跟大整数打交道。

/*************************************************************************
 ************************************************************************/
#include<iostream>
#include<string>
#include<stdint.h>
//#include<cstdint> // C++11
using namespace std;

bool Compare(string s1, string s2)
{
    unsigned int primeNum[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};
    uint64_t ch = 1;

    for(int i=0; i<s1.size(); ++i)
    {
        ch = ch*primeNum[s1[i]-'a'];
    }

    for(int i=0; i<s2.size(); ++i)
    {
        ch = ch/primeNum[s2[i]-'a'];
    }

    if(ch == 1)
        return true;
    else
        return false;
}

int main()
{
    string s1 = "abandon";
    string s2 = "banadon";
    if(Compare(s1, s2))
        cout << "They are brother words!" << endl;
    else
        cout << "They aren't brother words!" << endl;
    return 0;
}

思路二

将两个字符串按照字母表顺序排序，看排序后的字符串是否相等，如果相等则是兄弟字符串（变位词）。这种方法的时间效率根据你使用的排序算法不同而不同。当然，你可以自己写排序算法，这里我们使用C++的STL中的sort\(\)函数对字符串进行排序。

/*************************************************************************
 ************************************************************************/
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;

// 自定义序函数（二元谓词）
bool myfunction(char i, char j)
{
    return i > j;
}

bool Compare(string s1, string s2)
{
    // 采用泛型算法对s1,s2排序，sort()采用的是快速排序算法
    sort(s1.begin(), s1.end(), myfunction);
    sort(s2.begin(), s2.end(), myfunction);
    if(!s1.compare(s2))  // 相等返回0
        return true;
    else
        return false;
}

int main()
{
    string s1 = "abandon";
    string s2 = "banadon";
    if(Compare(s1, s2))
        cout << "They are brother words!" << endl;
    else
        cout << "They aren't brother words!" << endl;
    return 0;
}

三，字典找出所有变位词集合（重点）

(1) 问题描述：给定一个英语字典，找出其中的所有变位词集合。

(2) 解决方案：

• 思路一

  对于这个问题，最快想到的最直接的方法就是针对每一个单词跟字典中的其他单词进行比较。然而，假设一次比较至少花费1微秒的时间，则拥有二十万单词的字典将花费：200000单词 x 200000比较/单词 x 1微秒/比较 = 40000x10^6秒 = 40000秒 ≈ 11.1小时。比较的次数太多了，导致效率低下，我们需要找出效率更高的方法。

• 思路二

  标识字典中的每一个单词，使得在相同变位词类中的单词具有相同的的标识，然后集中具有相同标识的单词。将每个单词按照字母表排序，排序后得到的字符串作为该单词的标识。那么对于该问题的解题过程可以分为三步：第一步，读入字典文件，对单词进行排序得到标识；第二步，将所有的单词按照其标识的顺序排序；第三步，将同一个变位词类中的各个单词放到同一行中。

这里出现了标识-单词（key-value）对，我们很容易想到C++中的关联容器map，使用map的好处就是：

• 动态管理内存，容器大小动态改变；

• 单词与它的标识一一对应，对于相同标识(key)的单词直接加在值(value)后面；

• 无需根据标识排序，因为map会自动按关键字有序（默认升序）。

所以，在将每个单词及其标识存入map以后，就可以直接遍历输出了，每一个map元素就是一个变位词集合。

C++代码：

/*************************************************************************
 ************************************************************************/
#include<iostream>
#include<fstream>    // file I/O
#include<map>        // map
#include<string>     // string
#include<algorithm>  // sort
using namespace std;
/*
 *map是C++中的关联容器
 *     按关键字有序
 *     关键字不可重复
 */
map<string, string> word;

/* 自定义比较函数（用于排序） */
bool myfunction(char i, char j)
{
    return i < j;
}

/* 
 *对每个单词排序
 *排序后字符串作为关键字，原单词作为值
 *存入map中
 */
void sign_sort(const char* dic)
{
    // 文件流
    ifstream in(dic);
    if(!in)
    {
        cout << "Couldn't open file: " + string(dic) << endl;
        return;
    }

    string aword;
    string asign;
    while(in >> aword)
    {
        asign = aword;
        sort(asign.begin(), asign.end(), myfunction);
        // 若标识不存在，创建一个新map元素，若存在，加在值后面
        word[asign] += aword + " ";
    }
    in.close();
}

/*
 *写入输出文件
 */
void write_file(const char* file)
{
    ofstream out(file);
    if(!out)
    {
        cout << "Couldn't create file: " + string(file) << endl;
        return;
    }

    map<string, string>::iterator begin = word.begin();
    map<string, string>::iterator end = word.end();
    while(begin != end)
    {
        out << begin->second << "\n";
        ++begin;
    }
    out.close();
}

int main()
{
    string dic;  
    string outfile;

    cout << "Please input dictionary name: ";
    cin >> dic;
    cout << "Please input output filename: ";
    cin >> outfile;

    sign_sort(dic.c_str());
    write_file(outfile.c_str());

    return 0;
}

附：（2012.5.6百度实习笔试题）一个单词交换字母位置，可得另一个单词，如army->mary，成为兄弟单词。提供一个单词，在字典中找到它的兄弟。描述数据结构和查询过程。

解题思路：如果不允许进行预处理，那么我们只能顺序遍历整个字典，计算每个单词的标识与给定单词的标识比较。如果允许进行预处理，我们可以如上述思路二将所有单词加入一个map，然后输出关键字（给定单词的标识）对应的值，值中就包含了该单词的所有兄弟单词。