Solution to LeetCode Problems: Anagrams

Anagrams

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

Note: All inputs will be in lower-case.

Thoughts:

What is the definition of anagrams?
One thing has to be thought over: do "" and "" together make a pair of anagrams?

After we defined anagrams, the algorithm straight in the mind is hash. What is a good hash algorithm? There are several possibilities. Two of them are: 1. hash by sorting the string; 2. hash by counting the number of used characters, respectively. The latter is used in the solution.

Solution:

1. class Solution {  
2. public:  
3.     struct StringHash  
4.     {  
5.         char hash[26];  
6.           
7.         StringHash(const string& str)  
8.         {  
9.             fill(hash, hash+26, 0);  
10.             for(auto& ch : str)  
11.                 ++ hash[ch - 'a'];  
12.         }  
13.           
14.         bool operator<(const StringHash& sh) const  
15.         {  
16.             for(size_t i = 0; i < 26; ++i)  
17.                 if ( this->hash[i] < sh.hash[i] )  
18.                     return true;  
19.                 else if ( this->hash[i] > sh.hash[i] )  
20.                     return false;  
21.             return false;  
22.         }  
23.     };  
24.   
25.     vector<string> anagrams(vector<string> &strs)   
26.     {  
27.         map<StringHash, vector<vector<string>::iterator>>  hash_map;  
28.   
29.         for(auto iter=begin(strs); iter != end(strs); ++iter)  
30.             hash_map[StringHash(*iter)].push_back(iter);  
31.   
32.         vector<string> ret;  
33.         for(auto hsm : hash_map)  
34.             if (hsm.second.size() >= 2)  
35.                 for(auto i : hsm.second)  
36.                     ret.push_back(*i);  
37.   
38.         return ret;  
39.     }