SprintCode.pro
Подготовка к алгоритмическим задачам

Группировка анаграмм: разбор задачи
Почему эта задача важна?
Задача на группировку анаграмм позволяет оценить:
- Умение работать со строками и хеш-таблицами
- Навыки оптимизации алгоритмов
- Способность находить эффективные способы группировки данных
- Понимание различных методов сравнения строк
Постановка задачи
Формулировка:
Дан массив строк. Необходимо сгруппировать все анаграммы вместе и вернуть массив групп анаграмм.
Примеры:
// Первый пример Input: strs = ['eat', 'tea', 'tan', 'ate', 'nat', 'bat'] Output: [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']] // Второй пример Input: strs = [''] Output: [['']] // Третий пример Input: strs = ['a'] Output: [['a']]
Подходы к решению
Решение 1: Сортировка символов (базовый подход)
function groupAnagrams(strs) { const groups = new Map() for (const str of strs) { const sorted = str.split('').sort().join('') if (!groups.has(sorted)) { groups.set(sorted, []) } groups.get(sorted).push(str) } return Array.from(groups.values()) }
Анализ решения:
✅ Простая и понятная реализация
✅ Надёжно работает для всех случаев
❌ Временная сложность O(n _ k _ log k), где k - длина строки
❌ Излишние операции сортировки
Пройди собеседование в топ-компанию
Платформа для подготовки
Решай алгоритмические задачи как профи

Решение 2: Подсчёт символов
function groupAnagrams(strs) { const groups = new Map() for (const str of strs) { const count = new Array(26).fill(0) for (const char of str) { count[char.charCodeAt(0) - 'a'.charCodeAt(0)]++ } const key = count.join('#') if (!groups.has(key)) { groups.set(key, []) } groups.get(key).push(str) } return Array.from(groups.values()) }
Характеристики:
✅ Оптимальная временная сложность O(n * k)
✅ Не требует сортировки
✅ Эффективное использование памяти
❌ Работает только с нижним регистром латинских букв
Решение 3: Хеширование простыми числами
function groupAnagrams(strs) { const primes = [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, ] const groups = new Map() for (const str of strs) { let hash = 1 for (const char of str) { hash *= primes[char.charCodeAt(0) - 'a'.charCodeAt(0)] } if (!groups.has(hash)) { groups.set(hash, []) } groups.get(hash).push(str) } return Array.from(groups.values()) }
Преимущества и недостатки:
✅ Очень быстрая работа O(n * k)
✅ Компактный код
❌ Возможно переполнение для длинных строк
❌ Ограничено размером алфавита
Рекомендации по решению
-
Выбор метода решения:
- Сортировка символов - для небольших строк
- Подсчёт символов - для больших наборов данных
- Хеширование - когда важна скорость
-
Важные моменты:
- Обработка пустых строк
- Учёт регистра букв
- Эффективное хранение групп
Распространённые ошибки
- Неправильная обработка пустых строк
- Избыточные операции сортировки
- Неучтённое переполнение при хешировании
Оптимизации
Оптимизация для коротких строк
function groupAnagrams(strs) { if (strs.length <= 1) return [strs] const groups = new Map() const isShort = strs.every((s) => s.length <= 3) for (const str of strs) { const key = isShort ? str.split('').sort().join('') : getCharCount(str) if (!groups.has(key)) { groups.set(key, []) } groups.get(key).push(str) } return Array.from(groups.values()) } function getCharCount(str) { const count = new Array(26).fill(0) for (const char of str) { count[char.charCodeAt(0) - 'a'.charCodeAt(0)]++ } return count.join('#') }
Заключение
При решении задачи важно учитывать:
- Различные способы представления анаграмм
- Баланс между скоростью и потреблением памяти
- Особенности входных данных
Эта задача показывает, как правильный выбор структур данных и метода сравнения строк может значительно влиять на производительность решения.