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

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

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

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

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

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

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

Примеры:

// Первый пример
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('#')
}

Заключение

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

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

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