康瑞部落

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<string> anagrams(vector<string>& strs) {
        vector<string> result;
        
        int len = strs.size();
        
        bool checked[len];
        memset(checked, 0, len*sizeof(bool));
        
        for(int i=0; i<len; i++){
            if(checked[i]){
                continue;
            }
            for(int j=i+1; j<len; j++){
                if(isAnagrams(strs[i], strs[j])){
                    if(!checked[i]){
                        result.push_back(strs[i]);
                    }
                    checked[i]=checked[j]=true;
                    result.push_back(strs[j]);
                }
            }
        }
        
        return result;
    }
    
    bool isAnagrams(string& s1, string& s2){
        if(s1.length()!=s2.length()){
            return false;
        }
        
        int letters[26];
        memset(letters, 0, 26*sizeof(int));
        
        for(int i=0; i<s1.length(); i++){
            letters[s1[i]-'a']++;
        }
        for(int j=0; j<s2.length(); j++){
            letters[s2[j]-'a']--;
            if(letters[s2[j]-'a']<0){
                return false;
            }
        }
        
        return true;
    }
};

另外一种办法，判断两个字符串是否互为变位字，首先将他们排序，若排序后他们相同，那么他们就是变位字。虽然单独判断的时间复杂度为O(nlogn)，但是这个信息能够重复利用。对于这道题就是如此。因此可以用一个hash表记录所有变位字。

class Solution {
public:
    vector<string> anagrams(vector<string>& strs) {
        vector<string> result;
        
        map<string, vector<string>> codeToStrs;
        int len = strs.size();
        for(int i=0; i<len; i++){
            string code = getCode(strs[i]);
            codeToStrs[code].push_back(strs[i]);
        }
        for(map<string, vector<string>>::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;
    }
};