程序员面试金典

程序员面试金典--变位词排序

题目描述

请编写一个方法，对一个字符串数组进行排序，将所有变位词合并，保留其字典序最小的一个串。这里的变位词指变换其字母顺序所构成的新的词或短语。例如"triangle"和"integral"就是变位词。

给定一个string的数组str和数组大小int n，请返回排序合并后的数组。保证字符串串长小于等于20，数组大小小于等于300。

测试样例：

["ab","ba","abc","cba"]

返回：["ab","abc"]

 

class SortString {
public:
    vector<string> sortStrings(vector<string> str, int n) {
        // write code here 
        sort(str.begin(), str.end()); 

        vector<string> ans; 
        map<string, int> mp; 
        for(int i=0; i<str.size(); ++i) {
            string tmp = str[i]; 
            sort(tmp.begin(), tmp.end()); 
            if(mp.find(tmp) == mp.end()){
                ans.push_back(str[i]); 
                mp[tmp] = 1; 
            }
        } 
        return ans; 
    }
};