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;
}
};