[LeetCode 49] Group Anagrams

Given an array of strings, group anagrams together.

For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"],

Return:

[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note:
For the return value, each inner list's elements must follow the lexicographic order. All inputs will be in lower-case.'

Diffculty
Medium

Similar Problems
[LeetCode ] Valid Anagram Easy [LeetCode ] Group Shifted Strings Easy

Analysis

分析： 所谓的anagrams，就是某个单词打乱其字母顺序形成的新单词， 新单词和原单词包含的字母种类相同，每个字母的数目相同。 注意这里有有一个重要特征： 对这些anagram单词排序后，这些单词都等于同一个单词了, 利用这个特征，我们先把当前单词排序，然后到map里去找，如果找到，则发现一个anagram

class Solution { public: vector> groupAnagrams(vector& strs) { vector> result;

    // 此处排序的目的是为了保证Note中提到的条件
    // 即inner list要按字母顺序排序
    std::sort(strs.begin(), strs.end());

    map<string, vector<string>> ht;
    for(int i = 0; i < (int)strs.size(); i++){
        string s = strs[i];
        std::sort(s.begin(), s.end());
        ht[s].push_back(strs[i]);
    }

    for(auto it = ht.begin(); it!= ht.end(); it++){
        result.push_back(it->second);
    }

    return result;
}

};

Anagrams指几个string有相同的字符，但不同的字符顺序。所以一个有效的检查方法是： 当两个string排序以后相同，则它们是anagrams。可以使用一个hash table， string s的key是它自己排序后的string，这样anagrams会有相同的key。 用一个vector来记录相同key的string在input vector中的index。 最后扫描一遍hash table，当有两个或以上string有相同的key时，将它们输出到结果。 class Solution { public: vector anagrams(vector &strs) { vector ret; unordered_map> ht;

    for(int i = 0; i < (int)strs.size(); i++) {
        string s = strs[i];
        sort(s.begin(), s.end());
        ht[s].push_back(i);
    }

    for(auto it = ht.begin(); it != ht.end(); it++){
        if(it->second.size() > 1) {
            for(int i = 0; i < it->second.size(); i++){
                ret.push_back(strs[it->second[i]]);
            }
        }
    }
    return ret;
}

};

原题目(现已改为Group Anagrams)： LeetCode: Anagrams Given an array of strings, return all groups of strings that are anagrams. Note: All inputs will be in lower-case.

For example: Input: ["tea","and","ate","eat","den"] Output: ["tea","ate","eat"]

分析： 用哈希map存储排序后的字符串，map中key为排序后字符串，value为该字符串对应的第一个原字符串在数组中的位置。 如果value = -1，表示该字符串对应的第一个源字符串已经输出过。

class Solution { public: vector anagrams(vector &strs) { typedef unordered_map Umap; Umap ht; vector sol; vector> res; for(int i = 0; i < strs.size(); i++){ string s = strs[i]; sort(s.begin(), s.end()); auto iter = ht.find(s); if(iter == ht.end()) // 不在map中，则是一个新的anagram ht.insert(Umap::value_type(s, i)); // std::make_pair(s, i) else{ if(iter->second != -1){ // 把value 设为-1来表示第一个插入的 sol.push_back(strs[iter->second]); iter->second = -1; } sol.push_back(strs[i]); } } return res; } };