Group Anagrams Problem


Description

LeetCode Problem 49.

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.

Example 1:

1
2
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Example 2:

1
2
Input: strs = [""]
Output: [[""]]

Example 3:

1
2
Input: strs = ["a"]
Output: [["a"]]

Constraints:

  • 1 <= strs.length <= 10^4
  • 0 <= strs[i].length <= 100
  • strs[i] consists of lowercase English letters.


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        int freq[26] = {0};
        map<string, int> ht;
        vector<vector<string>> ans;
        int idx = 0;
        
        for (int i = 0; i < strs.size(); i ++) {
            for (int j = 0; j < 26; j ++)
                freq[j] = 0;
            for (int j = 0; j < strs[i].size(); j ++) {
                freq[strs[i][j] - 'a'] ++;
            }
            string s = "";
            for (int j = 0; j < 26; j ++) {
                s += to_string(j) + to_string(freq[j]);
            }
            if (ht.find(s) == ht.end()) {
                ht[s] = idx;
                idx ++;
                vector<string> line;
                ans.push_back(line);
            }
            ans[ht[s]].push_back(strs[i]);
        }
        return ans;
    }
};




Related Posts

X Of A Kind In A Deck Of Cards Problem

LeetCode 914. In a deck of cards, each card has...

Word Subsets Problem

LeetCode 916. You are given two string arrays words1 and...

Vowel Spellchecker Problem

LeetCode 966. Given a wordlist, we want to implement a...

Verifying An Alien Dictionary Problem

LeetCode 953. In an alien language, surprisingly, they also use...

Unique Morse Code Words Problem

LeetCode 804. International Morse Code defines a standard encoding where...

Unique Email Addresses Problem

LeetCode 929. Every valid email consists of a local name...