На этом шаге мы рассмотрим анаграммы - часто встречающийся при собеседованиях программистов вопрос на проверку кругозора в области компьютерных наук и умения разрабатывать собственные простые алгоритмы. На этом шаге мы расскажем о простом алгоритме для поиска анаграмм на языке Python.

Общее описание

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

• listen → silent;
• funeral → real fun;
• elvis → lives.

Рис.1. Слово elvis - анаграмма слова lives

    Займемся этой задачей и найдем лаконичное решение в стиле Python для определения того, являются ли два слова анаграммами. Что ж, приступим к написанию кода.

Код

    Наша задача - написать функцию is_anagram(), которая принимает на входе два строковых значения х1 и х2 и возвращает True, если они - анаграммы! Прежде чем продолжить чтение, на минуту задумайтесь об этой задаче. Как бы вы стали решать ее на Python? Одно из возможных решений приведено в примере 6.1.

## Однострочник
(1) is_anagram = lambda x1, x2: sorted(x1) == sorted(x2)

## Результат
print(is_anagram("elvis", "lives"))
print(is_anagram("elvise", "livees"))
print(is_anagram("elvis", "dead"))

    Этот код выводит три строки. Какие?

Принцип работы

    Два строковых значения - анаграммы, если у них совпадают отсортированные последовательности символов, так что мы сортируем их и сравниваем поэлементно. Это несложно и не требует никаких внешних зависимостей. Просто создаем функцию is_anagram() (1) путем описания лямбда-функции с двумя аргументами x1 и x2, которая возвращает результат выражения sorted(x1) == sorted(x2) - True, если отсортированные последовательности символов совпадают. Ниже представлен результат сортировки двух последовательностей символов:

print(sorted("elvis"))
# ['e', 'i', 'l', 's', 'v']

print(sorted("lives"))
# ['e', 'i', 'l', 's', 'v']

    Обе строки 'elvis' и 'lives' состоят из одних символов, так что их представления в виде отсортированного списка одинаковы. Результаты вышеприведенных трех операторов print:

## Результат
print(is_anagram("elvis", "lives"))   # True
print(is_anagram("elvise", "livees")) # True
print(is_anagram("elvis", "dead"))    # False

    В качестве небольшого примечания для опытных программистов скажем вот что: сложность сортировки последовательности n элементов на языке Python растет асимтотически, как функция от n*log(n). Это означает, что наш однострочный алгоритм эффективнее "наивного" решения, состоящего в проверке наличия каждого символа в обоих строковых значениях и его удаления в этом случае. Сложность "наивного" алгоритма растет асимтотически, как квадратичная функция n**2.

    Однако существует и другой эффективный способ решения этой задачи - создание гистограмм для обоих строковых значений на основе подсчета количества вхождений всех символов строки с последующим сравнением обеих гистограмм. Если размер алфавита не меняется, то сложность вычисления при таком подходе линейна и растет асимптотически как функция n. Оставляем реализацию этого алгоритма в качестве маленького упражнения!

    На следующем шаге мы рассмотрим поиск палиндромов с помощью лямбда-функций и негативных срезов.

Предыдущий шаг Содержание Следующий шаг