На этот раз будем изучать задачу «Проверка анаграмм» («Verify Anagrams»).
Мы уже писали об этой задаче ранее, но теперь расскажем о ней немного другим способом.
Анаграмма — это игра со словами, когда в результате перестановки букв слова или фразы получаем другое слово или фразу. Два слова являются анаграммами, если мы можем получить одно из другого переставляя буквы местами. Даны два слова или фразы, и ваша задача — проверить, являются ли они анаграммами.
Считаем буквы
Итак, нам нужно сравнить две фразы. Для начала нам нужно их «обработать»: выбрать только буквы и перевести их в нижний регистр. Также, на этом шаге мы можем преобразовать строку в массив. Вынесем эту процедуру в отдельную функцию.
1 2 | def sanitize(text): return [ch.lower() for ch in text if ch.isalpha()] |
Или, если вы бережете память и предпочитаете генераторы:
1 2 | def sanitize(text): yield from (ch.lower() for ch in text.lower() if ch.isalpha()) |
Или любите функциональный стиль программирования:
1 | sanitize = lambda t: map(str.lower, filter(str.isalpha, text)) |
Далее нам нужно сосчитать каждую букву в тексте, и, если количественные характеристики проверяемых слов/фраз совпадают, то они анаграммы. Предположим, что мы используем только английские буквы. Тогда мы можем использовать массив из 26 элементов для ведения счета.
1 2 3 4 5 | def count_letters(text): counter = [0] * 26 for ch in text: counter[ord(ch) - ord("a")] += 1 return counter |
Честно говоря, это выглядит как код написанный на С, но никак не на Python. Кроме того, мы привязаны жестко к английскому алфавиту. Давайте заменим список на словарь (dictionary).
1 2 3 4 5 | def count_letters(text): counter = {} for ch in text: counter[ch] = counter.get(ch, 0) + 1 return counter |
Уже лучше, но известный девиз Python гласит — «Батарейки прилагаются». И класс Counter дает возможность просто подсчитать буквы в тексте.
1 2 3 4 | from collections import Counter def count_letters(text): return Counter(text) |
Думаю, вы и сами видите, что наша отдельная функция count_letters уже не так уж и нужна, и итоговое решение можно записать так:
1 2 3 4 5 6 7 | 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)) |
Сортируем все подряд
Когда я решал первый раз эту задачу, я не использовал счетчики. Вместо этого я преобразовывал текст в некий универсальный вид для перестановок. Конечно, я говорю об упорядоченном виде. Если мы отсортируем строки и сравним их, то это по сути то же самое, что считать элементы массива. И, так как в нашей задаче текст содержит только буквы и пробелы, то можно использовать один трюк:
1 2 | def verify_anagrams(first, second): return "".join(sorted(first.lower())).strip() == "".join(sorted(second.lower())).strip() |
Как можно заметить, мы одним движением руки можем преобразовать эту функцию в однострочник (забавы ради):
1 | verify_anagrams=lambda f,s,p=lambda x: "".join(sorted(x.lower())).strip():p(f)==p(s) |
Вот такая вот история об анаграммах.
Спасибо CheckiO за интересную задачу.
