LeetCode Daily Question 2

3 月 6 日 每日一题

题目：49. Group Anagrams

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

eg: Input: Input: strs = [“eat”,”tea”,”tan”,”ate”,”nat”,”bat”]
Output: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]

思路

使用 count sort，以避免对每一个 str 进行 sort。首先建立一个对于 26 个字母的 count[26]，记录每个字母出现的次数，并且返回一个形式为 a2b2(abab)的 key。使用一个 unorder map 储存 <key,vector>，并且在最后把 vector 导入新建的 vector<vector> res。
时间复杂度为 O(mn) 空间复杂度为 O(26m)，m 为 str 数目，n 为单个 str 长度。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> groups;
    for(auto str: strs){
        groups[getKey(str)].push_back(str);
        }
    vector<vector<string>> res;
    for(auto ele: groups){
        res.push_back(ele.second);
    }
    return res;
}

string getKey(string str){
    int count[26] = {0};
    for(auto s:str){
        count[s-'a']++;
    }
    string key;
    for(int i = 0; i < 26; i++){
        if(count[i] > 0)
        key += char(i + 'a') + to_string(count[i]);
    }
    return key;
}