SprintCode.pro

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

Super

Группировка анаграмм: разбор задачи

12 мин чтения
алгоритмы
строки
хеширование

Почему эта задача важна?

Задача на группировку анаграмм позволяет оценить:

  • Умение работать со строками и хеш-таблицами
  • Навыки оптимизации алгоритмов
  • Способность находить эффективные способы группировки данных
  • Понимание различных методов сравнения строк

Постановка задачи

Формулировка:

Дан массив строк. Необходимо сгруппировать все анаграммы вместе и вернуть массив групп анаграмм.

Примеры:

// Первый пример 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 - длина строки

❌ Излишние операции сортировки

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь
Начать сейчас
Программист за работой

Решение 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)

✅ Компактный код

❌ Возможно переполнение для длинных строк

❌ Ограничено размером алфавита

Рекомендации по решению

  1. Выбор метода решения:

    • Сортировка символов - для небольших строк
    • Подсчёт символов - для больших наборов данных
    • Хеширование - когда важна скорость
  2. Важные моменты:

    • Обработка пустых строк
    • Учёт регистра букв
    • Эффективное хранение групп

Распространённые ошибки

  1. Неправильная обработка пустых строк
  2. Избыточные операции сортировки
  3. Неучтённое переполнение при хешировании

Оптимизации

Оптимизация для коротких строк

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('#') }

Заключение

При решении задачи важно учитывать:

  • Различные способы представления анаграмм
  • Баланс между скоростью и потреблением памяти
  • Особенности входных данных

Эта задача показывает, как правильный выбор структур данных и метода сравнения строк может значительно влиять на производительность решения.