学步园

Note: All inputs will be in lower-case.

思路：

关键在于对题目的理解。本文中anagrams指只有字母排列顺序不同的单词，例如eat，ate，tea。倘若有多组anagrams，那么返回所有的anagrams。两个空字符串也算一对anagrams。那么这个问题就可以使用hash的方法来解决。有很多种不同的hash方法，可以马上想到的有排过序的字符串作为hash key，或者按字母计数生成一个hash key。这里采用后者。

题解：

class Solution {
public:
    struct StringHash
    {
        char hash[26];
        
        StringHash(const string& str)
        {
            fill(hash, hash+26, 0);
            for(auto& ch : str)
                ++ hash[ch - 'a'];
        }
        
        bool operator<(const StringHash& sh) const
        {
            for(size_t i = 0; i < 26; ++i)
                if ( this->hash[i] < sh.hash[i] )
                    return true;
                else if ( this->hash[i] > sh.hash[i] )
                    return false;
            return false;
        }
    };

    vector<string> anagrams(vector<string> &strs) 
    {
        map<StringHash, vector<vector<string>::iterator>>  hash_map;

        for(auto iter=begin(strs); iter != end(strs); ++iter)
            hash_map[StringHash(*iter)].push_back(iter);

        vector<string> ret;
        for(auto hsm : hash_map)
            if (hsm.second.size() >= 2)
                for(auto i : hsm.second)
                    ret.push_back(*i);

        return ret;
    }