Поиск анаграмм: алгоритм и реализация на Python

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

В этой статье мы разберём, что такое анаграмма, рассмотрим алгоритм её поиска и реализуем решение на Python с подробным объяснением кода.

Что такое анаграмма?

Анаграмма — это способ образования новых слов путём перестановки букв другого, заданного слова.

Например: кабан => банка; кот => ток

Этот принцип часто используется в головоломках и тестах на логику. Задача поиска анаграмм — популярное задание для лайвкодинга на собеседованиях Python-разработчиков.

Условие задачи на поиск анаграмм

Обычно задание звучит следующим образом:

Написать метод для поиска анаграмм. На вход методу нужно передать список слов, на выходе — получить списком слова, являющимися анаграммами.

Пример решения

from collections import defaultdict

def find_anagrams(*, original_word: list[str]) -> list[str]:
    anagram_groups = defaultdict(list)

    for word in original_word:
        sorted_word = "".join(sorted(word))
        anagram_groups[sorted_word].append(word)

    result = [group[0] for group in anagram_groups.values() if len(group) > 1]

    return result

>>> words = ["aba", "bac", "abb", "bab", "bba", "aab", "abca"]
>>> find_anagrams(original_word=words)

Объяснение кода

Разберём алгоритм поиска анаграмм на Python пошагово:

• Импортируем defaultdict из модуля collections, который создает словарь со значениями по умолчанию для несуществующих ключей.
• Определяем функцию find_anagrams, которая принимает один именованный аргумент original_word — это список строк (слов). Будем возвращать список строк.
• Используем defaultdict для создания словаря anagram_groups, где ключи будут отсортированными буквами слов, а значения — списками слов, которые являются анаграммами друг друга.
• Циклом проходимся по каждому слову из original_word. В каждой итерации слово сортируется по буквам (чтобы все анаграммы имели одинаковый ключ), и это отсортированное слово используется как ключ для добавления оригинального слова в anagram_groups.

Формируем новый список result, который заполняется первым словом из каждой группы анаграмм, если в этой группе больше одного слова.

Рассмотренный алгоритм поиска анаграмм показывает, как с минимальными затратами вычислительных ресурсов группировать слова по их составу. Использование defaultdict упрощает работу со словарями, а сортировка строк позволяет эффективно находить совпадения.

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

Если у вас есть идеи по улучшению кода или более эффективные способы решения этой задачи, делитесь ими.