Проверка анаграмм

  • , Задачки
  • 2 минуты

На этот раз будем изучать задачу «Проверка анаграмм» («Verify Anagrams»).

Мы уже писали об этой задаче ранее, но теперь расскажем о ней немного другим способом.

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

Считаем буквы

Итак, нам нужно сравнить две фразы. Для начала нам нужно их «обработать»: выбрать только буквы и перевести их в нижний регистр. Также, на этом шаге мы можем преобразовать строку в массив. Вынесем эту процедуру в отдельную функцию.

def sanitize(text):
    return [ch.lower() for ch in text if ch.isalpha()]

Или, если вы бережете память и предпочитаете генераторы:

def sanitize(text):
    yield from (ch.lower() for ch in text.lower() if ch.isalpha())

Или любите функциональный стиль программирования:

sanitize = lambda t: map(str.lower, filter(str.isalpha, text))

Далее нам нужно сосчитать каждую букву в тексте, и, если количественные характеристики проверяемых слов/фраз совпадают, то они анаграммы. Предположим, что мы используем только английские буквы. Тогда мы можем использовать массив из 26 элементов для ведения счета.

def count_letters(text):
    counter = [0] * 26
    for ch in text:
        counter[ord(ch) - ord("a")] += 1
    return counter

Честно говоря, это выглядит как код написанный на С, но никак не на Python. Кроме того, мы привязаны жестко к английскому алфавиту. Давайте заменим список на словарь (dictionary).

def count_letters(text):
    counter = {}
    for ch in text:
        counter[ch] = counter.get(ch, 0) + 1
    return counter

Уже лучше, но известный девиз Python гласит — «Батарейки прилагаются». И класс Counter дает возможность просто подсчитать буквы в тексте.

from collections import Counter

def count_letters(text):
    return Counter(text)

Думаю, вы и сами видите, что наша отдельная функция count_letters уже не так уж и нужна, и итоговое решение можно записать так:

from collections import Counter

def sanitize(text):
    yield from (ch.lower() for ch in text.lower() if ch.isalpha())

def verify_anagrams(first, second):
    return Counter(sanitize(first)) == Counter(sanitize(second))

Сортируем все подряд

Когда я решал первый раз эту задачу, я не использовал счетчики. Вместо этого я преобразовывал текст в некий универсальный вид для перестановок. Конечно, я говорю об упорядоченном виде. Если мы отсортируем строки и сравним их, то это по сути то же самое, что считать элементы массива. И, так как в нашей задаче текст содержит только буквы и пробелы, то можно использовать один трюк:

def verify_anagrams(first, second):
    return "".join(sorted(first.lower())).strip() == "".join(sorted(second.lower())).strip()

Как можно заметить, мы одним движением руки можем преобразовать эту функцию в однострочник (забавы ради):

verify_anagrams=lambda f,s,p=lambda x: "".join(sorted(x.lower())).strip():p(f)==p(s)

Вот такая вот история об анаграммах.

Спасибо CheckiO за интересную задачу.