49. Group Anagrams

Prompt

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

Constraints:

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

Examples

• Example 1:
  • Input: strs = [“eat”,“tea”,“tan”,“ate”,“nat”,“bat”]
  • Output: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]
  • Explanation:
    • There is no string in strs that can be rearranged to form "bat".
    • The strings "nat" and "tan" are anagrams as they can be rearranged to form each other.
    • The strings "ate", "eat", and "tea" are anagrams as they can be rearranged to form each other.
• Example 2:
  • Input: strs = [""]
  • Output: ""
• Example 3:
  • Input: strs = [“a”]
  • Output: “a”

Solutions

Sorted String Keyed HashMap Solution

In C++

vector<vector<string>> groupAnagrams(vector<string>& strs) {
	unordered_map<string, vector<string>>
		sorted_word_to_anagrams;
	for (const auto& str : strs) {
		string sorted_str(str);
		sort(sorted_str.begin(), sorted_str.end());
		sorted_word_to_anagrams[sorted_str].push_back(str);
	}
 
	vector<vector<string>> result;
	for (const auto& pair : sorted_word_to_anagrams) {
		result.push_back(move(pair.second));
	}
	return result;
}

Explanation

We use sorting as a perfect Hash Function for anagrams that is guaranteed to have no collisions. The price of no collisions ever is worse time complexity. We have a HashMap between the sorted strings and lists of anagrams. After we finish the map, we extract all the KV-values, and return the resulting list of lists. Note that we make sure to avoiding copying by moving each list into the final list.

Big O Analysis

• Let $n$ be the number of strings in the input array
• Let $k$ be the maximum string length

Time Complexity

The time complexity is $O(n\cdot k\log k)$ because our keys take $k\log k$ to create, and we construct $n$ keys.

Auxiliary Space Complexity

The space complexity is $O(n\cdot k)$.

Boost Hash Combine Custom Frequency Map Keyed HashMap Solution

In C++

struct Key {
    int freq[26] = {};
    Key(string str) {
        for (char c : str) ++freq[c - 'a'];
    }
    bool operator==(const Key& other) const {
        return memcmp(this->freq, other.freq, 26 * sizeof(int)) == 0;
    }
};
 
namespace std {
    template <>
    struct hash<Key> {
        size_t operator()(const Key& k) const {
            size_t h = 0;
            for (int i = 0; i < 26; i++) {
                h ^= hash<int>{}(k.freq[i]) + 0x9e3779b9 + (h << 6) + (h >> 2);
            }
            return h;
        }
    };
}
 
vector<vector<string>> groupAnagrams(vector<string>& strs) {
	unordered_map<Key, vector<string>> strhash_to_anagrams;
	for (const auto& str : strs) {
		strhash_to_anagrams[Key(str)].push_back(str);
	}
	vector<vector<string>> result;
	for (const auto& pair : strhash_to_anagrams) {
		result.push_back(std::move(pair.second));
	}
	return result;
}

Explanation

This solution is the same as the previous but we use better keys than just the sorted string; instead we use custom keys that contain a static array frequency map and use a better Hash Function called Boost Hash Combine.

Big O Analysis

• Let $n$ be the number of strings in the input array
• Let $k$ be the maximum string length

Time Complexity

The time complexity is $O(n\cdot k)$ because our keys only take $O(k)$ to construct.

Auxiliary Space Complexity

The space complexity is $O(n\cdot k)$.