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: All inputs will be in lower-case.

来源： https://leetcode.com/problems/anagrams/

分析

这里并没有要求每组 anagram 内部排序，所以只需要把 anagram放到同一组中即可，想到的方法是每种 anagram，都对应唯一的 key 值，这里看到有两种

1. 字母内部排序，得到以字母为key

2. 为26个英文字母，对应26个质数，

算法1

每个string排序当key，不考虑vector<string> 内部排序（使用vector<string>当value）

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> map;
        for(auto s: strs){
            string key = s;
            sort(key.begin(), key.end());
            map[key].push_back(s);
        }
        vector<vector<string>> anagrams;
        for(auto m:map){
            anagrams.push_back(m.second);
        }
        return anagrams;
    }
};

使用string排序当key，考虑vector<string>内部排序。（使用multiset当 value）

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, multiset<string>> map;
        for(auto s: strs){
            string key = s;
            sort(key.begin(), key.end());
            map[key].insert(s);
        }
        vector<vector<string>> anagrams;
        for(auto m:map){
            vector<string> anagram(m.second.begin(), m.second.end());
            anagrams.push_back(anagram);
        }
        return anagrams;
    }
};

算法2

使用26个质数对应26个字母，乘积作为 key值，

class Solution {
public:
    int prime[26] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103};
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<long, vector<string>> map;
        for(auto s: strs){
            map[hash_value(s)].push_back(s);
        }
        vector<vector<string>> result;
        for(auto m: map){
            result.push_back(m.second);
        }
        return result;
    }
     
    long hash_value(string s){
        long value = 1;
        for(auto c: s){
            value *=prime[c-'a'];
        }
        return value;
    }
};

null