49. Group Anagrams - cocoder39/coco39_LC GitHub Wiki

49. Group Anagrams

Notes 2022

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = collections.defaultdict(list)
        for word in strs:
            count = [0] * 26
            for ch in word:
                count[ord(ch) - ord('a')] += 1
            groups[tuple(count)].append(word)
        return groups.values()

=============================================================

same idea as group shifted strings, map the string to base mode by sorting the string.

Instead of using sort() from STL whose time complexity is O(n * log n), the getBase() method works like a bucket sort, of which the time complexity is O(n) where n is the length of string

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> mp;
        for (auto str : strs) {
            mp[strSort(str)].push_back(str); 
        }
        
        vector<vector<string>> res;
        for (auto item : mp) {
            res.push_back(item.second);
        }
        return res;
    }
private:
    string strSort(string& str) {
        vector<int> count(26);
        int len = str.length();
        for (int i = 0; i < len; i++) {
            count[str[i] - 'a']++;
        }
        
        string res;
        for (int i = 0; i < 26; i++) {
            res += string(count[i], 'a' + i);
        }
        return res;
    }
};
⚠️ **GitHub.com Fallback** ⚠️