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

Note: All inputs will be in lower-case.

这题最开始的思路是用map<string, vector<sting> >来保存与string对应的anagrams，然后有一张vector<string> word来保存key string，但问题是每次新的string要遍历word来进行比较是否存在，用的是一个count[26]来保存字符的个数，然后一一比较。

最后发现其实先把每个string按字母排个序，然后就能很方便的进行string的两两比较了。写了3个版本。

这题的关键是对每个string按字典对其char重新排序，这样就能方便的得出map<string, vector<string> >中的key了

把sort string作为key插入set来比较

1 class Solution { 2 private: 3     vector
     
       ret; 4     vector
      
        canUse; 5     set
       
         s; 6     map
        
          index; 7 public:     8     vector
         
           anagrams(vector
          
            &strs) { 9 // Start typing your C/C++ solution below10 // DO NOT write int main() function11 ret.clear();12 s.clear();13 14 vector
           
             sortStr(strs);15 16 canUse.resize(strs.size());17 18 for(int i = 0; i < canUse.size(); i++)19 canUse[i] = false;20 21 for(int i = 0; i < sortStr.size(); i++)22 sort(sortStr[i].begin(), sortStr[i].end());23 24 for(int i = 0; i < sortStr.size(); i++)25 if (s.count(sortStr[i]) > 0)26 {27 ret.push_back(strs[i]);28 canUse[index[sortStr[i]]] = true;29 }30 else31 {32 index[sortStr[i]] = i;33 s.insert(sortStr[i]);34 }35 36 37 for(int i = 0; i < canUse.size(); i++)38 if (canUse[i])39 ret.push_back(strs[index[sortStr[i]]]); 40 41 return ret;42 }43 };
           
          
         
        
       
      
     

sort string后，根据sort string来排序，找出同类的string

1 struct Node 2 { 3     string org; 4     string sortOrg; 5     Node(){} 6     Node(string &a, string &b):org(a), sortOrg(b){} 7 }; 8  9 bool comp(const Node &lhs, const Node &rhs)10 {11     return lhs.sortOrg < rhs.sortOrg;12 }13 14 class Solution {15 private:16     vector
     
       a;17     vector
      
        ret;18 public:19     vector
       
         anagrams(vector
        
          &strs) {20         // Start typing your C/C++ solution below21         // DO NOT write int main() function22         ret.clear();23         a.clear();24         if (strs.size() == 0)25             return ret;26             27         for(int i = 0; i < strs.size(); i++)28         {29             string sortStrs(strs[i]);30             sort(sortStrs.begin(), sortStrs.end());31             32             a.push_back(Node(strs[i], sortStrs));33         }34         35         sort(a.begin(), a.end(), comp);36         37         string key = "1";38         39         int start = -1;40         int end = 0;41         42         while(end < a.size())43         {44             if (key == a[end].sortOrg)45                 end++;46             else47             {48                 if (start + 1 != end)49                 {50                     for(int i = start; i < end; i++)51                         ret.push_back(a[i].org);52                 }53                 key = a[end].sortOrg;54                 start = end;55                 end++;56             }57         }58         59         if (start + 1 != end)60         {61             for(int i = start; i < end; i++)62                 ret.push_back(a[i].org);63         }64         65         return ret;66     }67 };
        
       
      
     

不用保存word，直接sort string后得出key

1 class Solution { 2 private: 3     vector
     
       ret; 4     map
      
        > m; 5 public: 6     vector
       
         anagrams(vector
        
          &strs) { 7         // Start typing your C/C++ solution below 8         // DO NOT write int main() function 9         ret.clear();10         m.clear();11         for(int i = 0; i < strs.size(); i++)12         {13             string sortStr(strs[i]);14             sort(sortStr.begin(), sortStr.end());15             16             m[sortStr].push_back(strs[i]);17         }18         19         for(map
         
           >::iterator iter = m.begin(); iter != m.end(); iter++)20         {21             if ((iter->second).size() > 1)22             {23                 for(int i = 0; i < (iter->second).size(); i++)24                     ret.push_back((iter->second)[i]);25             }26         }27         28         return ret;29     }30 };