Этот вопрос проверяет понимание работы со строками, частотами символов и базовых алгоритмических приёмов.
Анаграммы — это слова, содержащие одинаковые буквы в одинаковом количестве, но расположенные в другом порядке. Чтобы проверить, являются ли два слова анаграммами, можно сравнить их отсортированные версии или посчитать количество вхождений каждого символа. Если множества букв и их частоты совпадают — слова анаграммы. Любой из этих методов работает за время O(n).
Определение:
Анаграммы — это строки, которые используют одинаковый набор символов с одинаковой частотой, но могут отличаться порядком букв.
Например:
"listen" и "silent"
"evil" и "vile"
Если сортировать строки, анаграммы станут идентичными:
Python
def is_anagram(a: str, b: str) -> bool:
return sorted(a) == sorted(b)
Плюсы:
короткий и понятный код.
Минусы:
сортировка требует O(n log n), что чуть медленнее альтернатив.
Можно подсчитать количество каждого символа и сравнить словари:
Python
from collections import Counter
def is_anagram(a: str, b: str) -> bool:
return Counter(a) == Counter(b)
Преимущества:
работает за O(n);
хорошо подходит для больших строк.
Регистр: нужно ли игнорировать (A vs a)?
Пробелы: учитываем или нет?
Unicode: важно при разных алфавитах.
Часто делают предварительную нормализацию.
Поиск слов-перестановок;
задачи на хеширование и группировку;
алгоритмические задачи на интервью.
Анаграммы определяются равенством частот символов. Лучший алгоритм — сравнение Counter, дающий линейную сложность и простоту реализации.
