CatCoding

LeetCode: anagrams

2014-01-14

LeetCode 这个题目想出来一个好办法,题目的意思是输入一组字符串,把他们按照 Anagrams 归组出来,
Anagrams 的意思是字母相同,排列不同的两个字符串。

比如:

aabc
baac
cbaa

这些都是 anagrams 的。如果两个字符串是满足这种关系的,那么把字符串排序后的结果一定相同。因此想到用一个 map 去存来。

class Solution {
public:
    vector<string> anagrams(vector<string> &strs) {
        typedef map<string, vector<string> > Dict;
        vector<string> res;
        Dict S;
        for(int i=0; i<strs.size(); i++) {
            string tmp = strs[i];
            sort(tmp.begin(), tmp.end());
            if(S.find(tmp) == S.end()) {
                S[tmp] = vector<string>(1, strs[i]);
            } else {
                S[tmp].push_back(strs[i]);
            }
        }

        for(Dict::iterator it = S.begin(); it != S.end(); ++it) {
            vector<string>& vec = it->second;
            if(vec.size() <= 1) continue;
            res.insert(res.begin(), vec.begin(), vec.end());
        }
        return res;
    }
};

公号同步更新,欢迎关注👻