Группировка анаграмм

Группировка анаграмм

Описание задачи

Анаграмма — это слово или фраза, образованная из тех же букв, но в другом порядке. Например, "eat", "tea", "ate" — это анаграммы. Задача требует групп ировать все анаграммы из входного списка вместе.

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

Подход 1: Сортировка букв (рекомендуется)

Ключевая идея: анаграммы имеют одни и те же буквы. Если отсортировать буквы в слове, получим одинаковый результат для всех анаграмм.

from collections import defaultdict

def group_anagrams(strs: list[str]) -> list[list[str]]:
    # Словарь: отсортированные буквы -> список слов
    anagram_map = defaultdict(list)
    
    for word in strs:
        # Сортируем буквы и используем как ключ
        key = "".join(sorted(word))
        anagram_map[key].append(word)
    
    # Возвращаем значения (группы)
    return list(anagram_map.values())

# Примеры
print(group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))
# [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

print(group_anagrams(["a", ""]))
# [["a"], [""]]

print(group_anagrams(["ab", "ba", "abc", "cba"]))
# [["ab", "ba"], ["abc", "cba"]]

Логика:

1. Для каждого слова сортируем его буквы: "eat" → "aet"
2. Отсортированная строка становится ключом
3. Все слова с одинаковым ключом — анаграммы
4. Храним в defaultdict(list) для удобства
5. Возвращаем только значения (группы)

Сложность:

• Временная: O(n × k log k), где n — количество слов, k — средняя длина слова
• Пространственная: O(n × k) для хранения карты

Подход 2: Кодирование букв (оптимизация)

Вместо сортировки можно подсчитать количество каждой буквы:

def group_anagrams_v2(strs: list[str]) -> list[list[str]]:
    anagram_map = defaultdict(list)
    
    for word in strs:
        # Подсчитываем буквы
        char_count = [0] * 26
        for char in word:
            char_count[ord(char) - ord(a)] += 1
        
        # Ключ — кортеж с количеством букв
        key = tuple(char_count)
        anagram_map[key].append(word)
    
    return list(anagram_map.values())

print(group_anagrams_v2(["eat", "tea", "tan", "ate", "nat", "bat"]))
# [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

Преимущества:

• Избегаем сортировки (O(k log k) → O(k))
• Быстрее на коротких словах с большим алфавитом
• Гарантированно O(n × k) вместо O(n × k log k)

Подход 3: Простая реализация (для понимания)

Для собеседований полезно показать понимание логики:

def group_anagrams_simple(strs: list[str]) -> list[list[str]]:
    result = {}
    
    for word in strs:
        # Сортируем — это наша сигнатура анаграммы
        signature = "".join(sorted(word))
        
        # Если сигнатуры нет в словаре — создаём
        if signature not in result:
            result[signature] = []
        
        # Добавляем слово в группу
        result[signature].append(word)
    
    return list(result.values())

Тестирование

import unittest

class TestGroupAnagrams(unittest.TestCase):
    def setUp(self):
        self.solution = group_anagrams
    
    def test_basic(self):
        result = self.solution(["eat", "tea", "tan", "ate", "nat", "bat"])
        # Проверяем, что группы правильны
        self.assertEqual(len(result), 3)
        self.assertIn(["eat", "tea", "ate"], 
                      [sorted(group) for group in result])
    
    def test_empty(self):
        self.assertEqual(self.solution([]), [])
    
    def test_single(self):
        self.assertEqual(self.solution(["a"]), [["a"]])
    
    def test_no_anagrams(self):
        result = self.solution(["abc", "def", "ghi"])
        self.assertEqual(len(result), 3)
    
    def test_all_anagrams(self):
        result = self.solution(["abc", "bca", "cab"])
        self.assertEqual(len(result), 1)
        self.assertEqual(len(result[0]), 3)

Сравнение подходов

Практические применения

1. Автодополнение — находим все похожие слова
2. Проверка орфографии — поиск возможных исправлений
3. Словари — группировка по корневым словам
4. Криптография — поиск паттернов в шифротексте

Заключение

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