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

Короткий ответ

Две строки являются анаграммами, если содержат одни и те же символы с одинаковыми частотами. Простейший способ проверки на Python — сравнить отсортированные версии: sorted(s1) == sorted(s2). Более эффективный — подсчитать частоты символов через словарь или collections.Counter, что даёт линейное время.

Как это работает подробнее

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

• Сортировка. У анаграмм совпадают отсортированные последовательности символов, что даёт короткое решение, но сортировка стоит O(n log n).
• Длины строк. Строки разной длины не могут быть анаграммами, поэтому такую проверку выполняют первой.
• Словарь частот. Проход по строкам с подсчётом символов даёт O(n + m): остаётся сравнить полученные словари частот.
• Counter. collections.Counter сам подсчитывает вхождения, а сравнение двух Counter эквивалентно сравнению частот всех символов.
• Массив счётчиков. Для строчных букв латиницы хватает 26 ячеек: для первой строки счётчики увеличивают, для второй уменьшают, и если в конце все значения нулевые — строки анаграммы.

Пример кода

Проверка анаграмм: Counter и сортировкаКопировать

from collections import Counter
def are_anagrams(s1, s2):
    if len(s1) != len(s2):
        return False
    return Counter(s1) == Counter(s2)
def are_anagrams_sorted(s1, s2):
    return sorted(s1) == sorted(s2)
print(are_anagrams('geeks', 'kseeg'))       # True
print(are_anagrams('allergy', 'allergyy')) # False

Что использовать на практике

• Простое решение. Для коротких строк подойдёт сравнение отсортированных версий — код короткий и очевидный.
• Эффективное решение. Для длинных строк используй collections.Counter: линейное время и минимум кода.
• Ранний выход. Начинай с проверки длины строк — она мгновенно отсекает большинство пар.
• Уточни алфавит. Обычно задача ограничена строчными буквами латиницы; если алфавит шире, массив из 26 ячеек не подойдёт.

Подводные камни

• Равные наборы, разные частоты. Одинаковый набор символов с другой частотой, например с лишней буквой, — это не анаграмма.
• Регистр. «Geeks» и «geeks» при учёте регистра — разные строки, поэтому правила нормализации стоит оговорить заранее.
• Непустые строки. В условии обычно указано, что строки непустые; две пустые строки формально являются анаграммами — уточни трактовку.
• Сложность сортировки. На больших данных наивная сортировка O(n log n) уступает подсчёту частот за O(n).

Как отвечать на собеседовании

• Начать с определения: одинаковые символы с одинаковыми частотами → показать наивное решение через сортировку и раннюю проверку длин → затем эффективное через Counter или массив счётчиков → упомянуть ограничения на алфавит и регистр.