[LeetCode] Anagrams

Given an array of strings, return all groups of strings that are anagrams.

Note: All inputs will be in lower-case.

思路：

Anagrams指几个string有相同的字符，但不同的字符顺序。所以一个有效的检查方法是：当两个string排序以后相同，则它们是anagrams。可以使用一个hash table，string s的key是它自己排序后的string，这样anagrams会有相同的key。用一个vector<int>来记录相同key的string在input vector<string>中的index。最后扫描一遍hash table，当有两个或以上string有相同的key时，将它们输出到结果。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

class Solution { public: vector<string> anagrams(vector<string> &strs) { vector<string> ret; unordered_map<string,vector<int>> ht; for(int i=0; i<strs.size(); i++) { string key = strs[i]; sort(key.begin(),key.end()); ht[key].push_back(i); } for(unordered_map<string,vector<int>>::iterator it=ht.begin(); it!=ht.end(); it++) { if(it->second.size()>1) { for(int i=0; i<it->second.size(); i++) { ret.push_back(strs[it->second[i]]); } } } return ret; } };