MiddleCodeCommonNot answered yet
Group an array of strings into sets of anagrams
Given an array of strings, group them so that each group contains exactly the words that are anagrams of each other (one is a letter permutation of another).
Requirements:
- Each input word appears in exactly one group.
- Aim for efficiency over the brute-force all-pairs comparison.
std::vector<std::vector<std::string>> groupAnagrams(std::vector<std::string>& words) {
// your code here
}Write the implementation.
Give every word a canonical key shared by all its anagrams, then bucket words by key in a hash map. The key is either the word's sorted characters or a 26-entry character-count signature. Words with the same key are anagrams. Collect the map's values as the groups.
- ✗Sorting the array and hoping anagrams become adjacent, which they do not
- ✗Grouping by length or first letter, which collides non-anagrams
- ✗Falling back to O(n^2) pairwise permutation checks
- →Why is a 26-count signature a faster key than sorting each word?
- →How would you handle Unicode words where 26 buckets are not enough?
Contents
Task
Group strings into anagram sets, faster than all-pairs comparison.
Solution
#include <vector>
#include <string>
#include <unordered_map>
#include <array>
std::vector<std::vector<std::string>> groupAnagrams(std::vector<std::string>& words) {
std::unordered_map<std::string, std::vector<std::string>> buckets;
for (auto& w : words) {
std::array<int, 26> cnt{}; // count signature
for (char c : w) ++cnt[c - 'a'];
std::string key;
for (int i = 0; i < 26; ++i) { key += '#'; key += std::to_string(cnt[i]); }
buckets[key].push_back(w); // same key → anagrams
}
std::vector<std::vector<std::string>> res;
for (auto& [k, group] : buckets) res.push_back(std::move(group));
return res;
}Key points
- A canonical key (26-letter counts) is shared by all of a word's anagrams.
- Bucketing in a hash map gives the groups in O(total characters).
- Grouping by length or first letter collides non-anagrams.
Contents
