Cracking the coding interview--Q9.2

January 17, 2013
作者:Hawstein
出处:http://hawstein.com/posts/9.2.html
声明:本文采用以下协议进行授权: 自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 ,转载请注明作者及出处。

题目

原文:

Write a method to sort an array of strings so that all the anagrams are next to each other.

译文:

写一个函数对字符串数组排序,使得所有的变位词都相邻。

解答

首先,要弄清楚什么是变位词。变位词就是组成的字母相同,但顺序不一样的单词。 比如说:live和evil就是一对变位词。OK,那么这道题目的意思就很清楚了, 它并不要求我们将字符串数组中的字符串按字典序排序,否则我们直接调用STL中的sort 函数就可以了。它要求我们在排序的过程中,按照变位词的准则来排序。 这种情况下,我们还是可以调用sort函数,不过要自己写一个对比函数。 一般情况下我们如果要排序一个长度为n的数组A,我们可以这样调用sort:

sort(A, A+n);

但如果我们有一个数组P,里面每个元素都是一个结构体:person,我们想按照person 这个结构体中年龄age来排序,这时候我们就需要自己写一个对比函数cmp:

bool cmp(person p1, person p2){
	return p1.age < p2.age; 
}

然后这样调用sort函数:

sort(P, P+n, cmp);

OK,回到我们的题目,我们的对比函数需要将两个串先按字典序排序,然后再比较, 这样一来,变位词经过字典序排序后就是一样的了。当调用sort函数时将会被排在一起。

代码如下:

#include <iostream>
#include <algorithm>
using namespace std;

bool cmp(string s1, string s2){
    sort(&s1[0], &s1[0]+s1.length());
    sort(&s2[0], &s2[0]+s2.length());
    return s1 < s2;
}
int main(){
    string s[] = {
        "axyz", "abc", "yzax", "bac", "zyxa", "fg", "gf"
    };
    sort(s, s+7, cmp);
    for(int i=0; i<7; ++i)
        cout<<s[i]<<endl;
    return 0;
}

全书题解目录:

Cracking the coding interview–问题与解答

全书的C++代码托管在Github上:

https://github.com/Hawstein/cracking-the-coding-interview