49 Group Anagrams

Given an array of strings, group anagrams together.
For example, given:

["eat", "tea", "tan", "ate", "nat", "bat"],

Return:

[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note: All inputs will be in lower-case.

Solution

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        int n = strs.size();
        map<string, vector<int>> record;
        vector<vector<string>> res;
        for ( int i = 0; i <= n-1; i++ ) {
            string sorted = strs[i];
            sort(sorted.begin(), sorted.end());
            if ( record.find(sorted) == record.end() ) {
                vector<int> tmp(1, i);
                record[sorted] = tmp;
            }
            else record[sorted].push_back(i);
        }
        for ( auto it = record.begin(); it != record.end(); it++ ) {
            vector<string> tmp_res;
            int ntmp = it->second.size();
            for ( int i = 0; i<= ntmp-1; i++ ) tmp_res.push_back(strs[it->second[i]]);
            res.push_back(tmp_res);
        }
        return res;
    }
};

Notes

• Note the use of hashtable.
• Use sorting to test anagram.
• Note the syntax to go through an map:

  for ( auto it = record.begin(); it != record.end(); it++ ) {
          it->first ***
          it->second ***
  }