leetcode49 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:

For the return value, each inner list's elements must follow the lexicographic order.

All inputs will be in lower-case.

 1 class Solution {
 2 public:
 3     vector<vector<string> > groupAnagrams(vector<string>& strs) {
 4         sort(strs.begin(),strs.end());
 5         vector<vector<string> > ans;
 6         map<string,int> tmap;//string为单个字符串排序后的字符串，int为该类string的list在ans中下表位置
 7         map<string,int>::iterator iter;
 8         int size=strs.size();
 9         for(int i=0;i<size;i++)
10         {
11             string temp=strs[i];
12             sort(temp.begin(),temp.end());
13             iter=tmap.find(temp);
14             if(iter==tmap.end())
15             {
16                 vector<string> tv;
17                 tv.push_back(strs[i]);
18                 ans.push_back(tv);
19                 tmap[temp]=ans.size()-1;
20             }
21             else
22             {
23                 int p=iter->second;
24                 ans[p].push_back(strs[i]);
25             }
26         }
27         return ans;
28     }
29 };

View Code