?

Anagrams

?

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

Note: All inputs will be in lower-case.

解题思路：

anagrams（变位字）是指对于两个单词来说，长度相同，且构成的字符除了顺序可以不同外，个数都相同。如cinema和iceman就是变位字。

判断两个字符串（长度需要相同）是否为变位字的方法，可以先对一个字符串每种字符进行计数，然后遍历另外一个字符串，对相应的位作减操作。若其中某个字符的计数出现负数，则为非变位字，否则，他们互相为变位字。这种方法的时间复杂度为O（n）。但是每次都需要遍历这个字符串。按这种思路写的代码如下。产生超时。

?

class Solution {
public:
    vector
  
    anagrams(vector
   
    & strs) { vector
    
      result; int len = strs.size(); bool checked[len]; memset(checked, 0, len*sizeof(bool)); for(int i=0; i
     
      另外一种办法，判断两个字符串是否互为变位字，首先将他们排序，若排序后他们相同，那么他们就是变位字。虽然单独判断的时间复杂度为O(nlogn)，但是这个信息能够重复利用。对于这道题就是如此。因此可以用一个hash表记录所有变位字。
      
?
      
?
      
class Solution {
public:
    vector
       
         anagrams(vector
        
         & strs) { vector
         
           result; map
          
           > codeToStrs; int len = strs.size(); for(int i=0; i
           
            >::iterator it = codeToStrs.begin(); it!=codeToStrs.end(); it++){ if(it->second.size()<2){ continue; } result.insert(result.begin(), it->second.begin(), it->second.end()); } return result; } string getCode(string s){ std::sort(s.begin(), s.end()); return s; } };
           
          
         
        
       
 
      
 
      
 
      
?