[LeetCode] Anagrams

[LeetCode] Anagrams

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