MiddleКодЧастоЕщё не отвечали
Сгруппировать массив строк в наборы анаграмм
Дан массив строк. Сгруппируйте их так, чтобы каждая группа содержала ровно слова, являющиеся анаграммами друг друга (одно — перестановка букв другого).
Требования:
- Каждое входное слово попадает ровно в одну группу.
- Стремитесь к эффективности вместо перебора всех пар.
std::vector<std::vector<std::string>> groupAnagrams(std::vector<std::string>& words) {
// ваш код здесь
}Допишите реализацию.
Дайте каждому слову канонический ключ, общий для всех его анаграмм, затем раскладывайте слова по ключу в хеш-таблицу. Ключ — это либо отсортированные символы слова, либо сигнатура из 26 счётчиков символов. Слова с одним ключом — анаграммы. Собираем значения таблицы как группы.
- ✗Сортировать массив в надежде, что анаграммы станут соседними, чего не происходит
- ✗Группировать по длине или первой букве, что сталкивает неанаграммы
- ✗Сваливаться к O(n^2) попарным проверкам перестановок
- →Почему сигнатура из 26 счётчиков — более быстрый ключ, чем сортировка слова?
- →Как обработать Unicode-слова, где 26 корзин недостаточно?
Оглавление
Задача
Сгруппируйте строки в наборы анаграмм эффективнее перебора всех пар.
Решение
#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{}; // сигнатура счётчиков
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); // одинаковый ключ → анаграммы
}
std::vector<std::vector<std::string>> res;
for (auto& [k, group] : buckets) res.push_back(std::move(group));
return res;
}Ключевые моменты
- Канонический ключ (счётчики 26 букв) общий для всех анаграмм слова.
- Раскладка по хеш-таблице даёт группы за O(всех символов).
- Группировка по длине/первой букве сталкивает неанаграммы.
Оглавление
