---
title: Group Anagrams
difficulty: Medium
category: Hash Table
leetcode_id: 49
revision_count: 1
last_revision: 2026-09-12
---

# Group Anagrams

> **LeetCode:** [#49](https://leetcode.com/problems/group-anagrams/)
> **Сложность:** Medium
> **Категория:** Hash Table

## Условие

Дан массив строк `strs`. Сгруппировать анаграммы — вернуть список списков, где каждая группа содержит строки, являющиеся анаграммами друг друга. Порядок групп и строк внутри группы не важен.

```
Input:  strs = ["eat","tea","tan","ate","nat","bat"]  →  Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Input:  strs = [""]                                    →  Output: [[""]]
Input:  strs = ["a"]                                   →  Output: [["a"]]
```

## Ключевая идея

Две строки — анаграммы тогда и только тогда, когда их отсортированные формы совпадают (или их частотные сигнатуры совпадают). Используем хэш-таблицу: ключ = отсортированная строка (или частотный `#`-разделённый шаблон), значение = список оригиналов. За один проход собираем группы.

## Оценка сложности

- **Время:** O(n × k log k) — сортировка каждой строки (n — количество строк, k — максимальная длина строки). С частотным подходом O(n × k).
- **Память:** O(n × k) — хэш-таблица со всеми строками

## Решение (Ruby)

```ruby
# @param {String[]} strs
# @return {String[][]}
def group_anagrams(strs)
  groups = Hash.new { |h, k| h[k] = [] }

  strs.each do |s|
    key = s.chars.sort.join
    groups[key] << s
  end

  groups.values
end
```

> **Альтернативный ключ (частотный):** вместо сортировки можно собрать частотный массив из 26 элементов и превратить в строку через `#`-разделитель. Это даёт O(n × k) вместо O(n × k log k).

```ruby
def group_anagrams_count(strs)
  groups = Hash.new { |h, k| h[k] = [] }

  strs.each do |s|
    cnt = Array.new(26, 0)
    s.each_byte { |b| cnt[b - 97] += 1 }
    key = cnt.join('#')
    groups[key] << s
  end

  groups.values
end
```

## Разбор на примере

```
strs = ["eat","tea","tan","ate","nat","bat"]

groups = {}

"eat" → sorted = "aet" → groups["aet"] = ["eat"]
"tea" → sorted = "aet" → groups["aet"] = ["eat", "tea"]
"tan" → sorted = "ant" → groups["ant"] = ["tan"]
"ate" → sorted = "aet" → groups["aet"] = ["eat", "tea", "ate"]
"nat" → sorted = "ant" → groups["ant"] = ["tan", "nat"]
"bat" → sorted = "abt" → groups["abt"] = ["bat"]

groups.values → [["bat"], ["tan","nat"], ["eat","tea","ate"]]
```

## Edge Cases

- **Пустой массив** → возвращаем пустой массив `[]`
- **Одна пустая строка** `[""]` → `sorted("") == ""` → группы `{ "" => [""] }` → `[[""]]`
- **Все строки — анаграммы** → одна группа
- **Все строки уникальны** → каждая в своей группе
- **Разный регистр**: вход только lowercase, как указано в условии. Если бы был регистр — нужно `downcase`.
- **Огромный массив**: хэш-таблица растёт, но альтернатив нет (только тот же проход).

## Типичные ошибки

1. ❌ **Сортировка забывает `chars`**: `s.sort` не работает на String в Ruby (вызовет `NoMethodError`). Нужно `s.chars.sort.join`.
2. ❌ **Использовать массив как ключ хэша**: `groups[cnt] << s` где `cnt = [0]*26` — каждый раз новый объект, ключи не совпадут. Решение: `cnt.join('#')` или `cnt.hash`.
3. ❌ **Не использовать `Hash.new { ... }`**: если ключа нет, `groups[key] << s` упадёт. Можно и `(groups[key] ||= []) << s`, но блок короче.
4. ❌ **Забыть `#` в частотном ключе**: `cnt.join` без разделителя превратит `[1, 10]` и `[10, 1]` в одинаковую строку `"110"`.

## Альтернативные подходы

| Подход | Время | Память | Комментарий |
|--------|-------|--------|-------------|
| Brute-force (попарно) | O(n² × k) | O(n) | Сравниваем каждую строку с каждой — не используем |
| Sort key | O(n × k log k) | O(n × k) | **Простое и читаемое** решение. Идёт в production |
| **Count key (frequency)** | **O(n × k)** | **O(n × k)** | **Оптимальное по времени** — key = частотный массив через `#`-разделитель |
| Prime product key | O(n × k) | O(n × k) | Каждой букве — простое число, key = произведение. Коллизии теоретически возможны при переполнении, но на практике — ок |

## Заметки после повторения

_— Заполняется после каждой тренировки._