Что такое анаграммы и как алгоритмически определить, являются ли два слова анаграммами?

Question

Анаграммы — это слова, содержащие одинаковые буквы в одинаковом количестве, но расположенные в другом порядке. Чтобы проверить, являются ли два слова анаграммами, можно сравнить их отсортированные версии или посчитать количество вхождений каждого символа. Если множества букв и их частоты совпадают — слова анаграммы. Любой из этих методов работает за время O(n).

YeaHub · Accepted Answer

1. Что такое анаграммыОпределение:Анаграммы — это строки, которые используют одинаковый набор символов с одинаковой частотой, но могут отличаться порядком букв.Например:"listen" и "silent""evil" и "vile"1.1. Подход 1: сортировка строкЕсли сортировать строки, анаграммы станут идентичными:Pythondef is_anagram(a: str, b: str) -> bool:
    return sorted(a) == sorted(b)
Плюсы:короткий и понятный код.Минусы:сортировка требует O(n log n), что чуть медленнее альтернатив.1.2. Подход 2: частоты символов (лучший вариант)Можно подсчитать количество каждого символа и сравнить словари:Pythonfrom collections import Counter

def is_anagram(a: str, b: str) -> bool:
    return Counter(a) == Counter(b)
Преимущества:работает за O(n);хорошо подходит для больших строк.1.3. Особые случаиРегистр: нужно ли игнорировать (A vs a)?Пробелы: учитываем или нет?Unicode: важно при разных алфавитах.Часто делают предварительную нормализацию.1.4. Где это используетсяПоиск слов-перестановок;задачи на хеширование и группировку;алгоритмические задачи на интервью.Краткий выводАнаграммы определяются равенством частот символов. Лучший алгоритм — сравнение Counter, дающий линейную сложность и простоту реализации.