Grokking 75: Top Coding Interview Questions

0% completed

​

Solution: Group Anagrams

Problem Statement

Given a list of strings, the task is to group the anagrams together.

An anagram is a word or phrase formed by rearranging the letters of another, such as "cinema", formed from "iceman"

You can return the answer in any order.

Examples

Example 1:

  • Input: ["dog", "god", "hello"]
  • Output: [["dog", "god"], ["hello"]]
  • Justification: "dog" and "god" are anagrams, so they are grouped together. "hello" does not have any anagrams in the list, so it is in its own group.

Example 2:

  • Input: ["listen", "silent", "enlist"]
  • Output:

.....

.....

.....

Like the course? Get enrolled and start learning!
N

Nicholas Tinsley

· 2 years ago

Sorting the strings takes O(k log(k)), but just doing a pass on each string and counting each character only takes O(k) time. You just allocate an array the size of your character set, and increment the value at that character's index. Finally, you write that array to a string (O(1), as it's determined by the size of your character set), and use that string as the key.

L

lejafilip

· 2 years ago

    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        std::unordered_map<size_t, std::vector<std::string>> exist;
        std::vector<std::vector<std::string>> result;

        for(const auto& str : strs)
        {
            std::vector<int> hist(26,0);
            for(const auto& c : str)
            {
                hist[c - 'a']++;
            }

            size_t key = 0;
            for(const auto& c : hist)
            {
                key *= 31;
                key += c;
            }
            
            exist[key].push_back(str);
        }

        for(auto& [_, anagrams] : exist)
        {
            result.emplace_back(std::move(anagrams));
        }

        return result;
    }