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;
    }
};

 
转载请注明： » [LeetCode] Anagrams

<!--
                    

                    	

                        	

                            	
                            
                        
                        

                        	

                            	
相关博文：
                                

                                	
                                    	
                                        	
                                        
                                        
定制桌面成功案例
                                    
                                    
                                    	
                                        	
                                        
                                        
海量文档查同或聚类问题 -- Locality Sensitive Hash 算法 （转）
                                    
                                    
                                    	
                                        	
                                        
                                        
汉字转拼音c/c++源码，支持gb2312和utf8
                                    
                                    
                                    	
                                        	
                                        
                                        
数据库顶级会议——SIGMOD介绍
                                    
                                
                            
                        
                    
                    -->