分析

hash的使用

class Solution {
public:    
    /**
     * @param strs: A list of strings
     * @return: A list of strings
     */
    vector<string> anagrams(vector<string> &strs) {
        // write your code here
        unordered_map<string, int> index;
        unordered_map<string, int>::iterator it;
        vector<string> ret;
        vector<vector<string>> save;
        for (int i = 0; i < strs.size(); ++i) {
            vector<int> h(26, 0);
            for (int j = 0; j < strs[i].length(); ++j) {
                int dist = strs[i][j] - 'a';
                ++h[dist];
            }
            string s = hash(h);
            it = index.find(s);
            if (it != index.end()) {
                int id = it->second;
                save[id].push_back(strs[i]);
            } else {
                vector<string> vs;
                vs.push_back(strs[i]);
                save.push_back(vs);
                index.insert(make_pair(s, save.size() - 1));
            }
        }
        for (int i = 0; i < save.size(); ++i) {
            if (save[i].size() > 1) {
                for (int j = 0; j < save[i].size(); ++j) {
                    ret.push_back(save[i][j]);
                }
            }
        }
        return ret;
    }
    
    string hash(const vector<int> &h) {
        stringstream ss;
        for (int i = 0; i < 26; ++i) {
            if (h[i]) {
                char ch = 'a' + i;
                ss << ch;
                if (h[i] > 1) {
                    ss << h[i];
                }
            }
        }
        return ss.str();
    }
};