题目:
Given an array of strings, return all groups of strings that are anagrams.
Note: All inputs will be in lower-case.
代码:
class Solution { public: vector<string> anagrams(vector<string>& strs) { vector<string> ret; map<string,vector<int> > str_indexs; // trans strs to key (sorted string) and value (indexs of strs that have same key) pairs for ( size_t i = 0; i < strs.size(); ++i ) { string key = strs[i]; std::sort(key.begin(), key.end()); str_indexs[key].push_back(i); } // add the keys which occurs more than once for ( map<string,vector<int> >::iterator it = str_indexs.begin(); it!= str_indexs.end(); ++it ) { if ( it->second.size()>1 ) { for ( size_t k = 0; k < it->second.size(); ++k ) { ret.push_back(strs[it->second[k]]); } } } return ret; } };
tips:
对于std::map的使用还不太熟悉,接着这道题也熟悉一下。
这道题非常经典,直接搜的AC code。学习了一下,把看过的几个blog记录在下面。
http://bangbingsyb.blogspot.sg/2014/11/leetcode-anagrams.html
http://www.cnblogs.com/AnnieKim/archive/2013/04/25/3041982.html
================================================
第二次过这道题,忘记了算法了。这道题做法确实比较特殊。先把每个单词按照字典序进行排序,然后直接把单词作为hash table的key进行判断。
最后输出重复count大于1的字符。注意排序的时候,不要直接拿strs进行排序,否则没法返回结果了。
class Solution { public: vector<string> anagrams(vector<string>& strs) { map<string, vector<int> > string_count; for ( int i=0; i<strs.size(); ++i ) { string tmp = strs[i]; std::sort(tmp.begin(), tmp.end()); string_count[tmp].push_back(i); } vector<string> ret; for ( map<string, vector<int> >::iterator i=string_count.begin(); i!=string_count.end(); ++i ) { if ( i->second.size()>1 ) { for ( int j=0; j<i->second.size(); ++j ) { ret.push_back(strs[i->second[j]]); } } } return ret; } };
另外注意有个地方需要改进一下,最后往ret填充的时候,可以一个group一起insert了。
class Solution { public: vector<string> anagrams(vector<string>& strs) { map<string, vector<string> > string_count; for ( int i=0; i<strs.size(); ++i ) { string tmp = strs[i]; std::sort(tmp.begin(), tmp.end()); string_count[tmp].push_back(strs[i]); } vector<string> ret; for ( map<string, vector<string> >::iterator i=string_count.begin(); i!=string_count.end(); ++i ) { if ( i->second.size()>1 ) { ret.insert(ret.end(), i->second.begin(), i->second.end()); } } return ret; } };