#49 Group Anagrams

Niraj Pandkar included in LeetCode

2023-05-22 184 words One minute views

Contents

Link

https://leetcode.com/problems/group-anagrams/description/

Solution

Generating a custom key function is necessary.
- The custom key function in this case initializes a vector of 26 zeroes each represeting a letter in the alphabet.
- Each zero will be incremented by 1 giving us the count of letters in the given word.
Time analysis:
- All the strings in the input array are going to be tranversed once. O(N) where N is the total number of strings in the input array.
- If the max length of a string in the input array is k, the total time complexity of the given problem solution is O(Nk).

Code

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        map<vector<int>, vector<string>> anagram_list;
        for(auto &str: strs){
            anagram_list[getKey(str)].push_back(str);
        }

        vector<vector<string>> ans;
        for(auto &x: anagram_list){
            ans.push_back(x.second);
        }
        return ans;
    }

    vector<int> getKey(string str){
        vector<int> v(26, 0);

        for(auto &letter: str){
            v[letter - 'a'] += 1;
        }
        return v;
    }
};

Notes

Make sure to add 1 for each occurrence of letter in the word.