Как проверить анаграммы python

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

На этот раз будем изучать задачу «Проверка анаграмм» («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 за интересную задачу.

Источник

4 метода для поиска и проверки анаграмм в Python

В этом руководстве мы узнаем, как определить, являются ли данные строки анаграммой. Но сначала мы должны познакомиться с концепцией анаграммы.

Что такое анаграмма?

Анаграмма – это состояние, при котором одна строка или число переставляются таким образом; каждый символ измененной строки или числа должен быть частью другой строки или числа. Другими словами, строка называется анаграммой другой, если вторая является простой перестановкой первой строки. Например: Python и yphton являются анаграммами; Java и avaJ также являются анаграммами.

Давайте разберемся с описанием проблемы определения анаграммы:

• Получите строковые входные данные от пользователя и сохраните их в отдельных переменных.
• Используйте метод sort() для сортировки обеих строк в списки.
• Проверьте оба списка, образуют ли они анаграмму или нет.
• Распечатайте результат.
• Выход.

def anagramCheck2(str1,str2): # Convert string into lists list1 = list(str1) list2 = list(str2) # Sort the list value list1.sort() list2.sort() position = 0 matches = True while position < len(str1) and matches: if list1[position]==list2[position]: position = position + 1 else: matches = False return matches print(anagramCheck2('python','ythonp'))

В приведенном выше коде мы объявили метод anagramCheck(), который принимает в качестве аргумента две строки. Эти строки преобразуются в список для сортировки. Затем мы определили переменную позиции и присвоили ей ноль. На каждой итерации цикла while длина строки сравнивается со значением позиции. Каждый элемент обоих списков сравнивал друг друга и увеличивал значение позиции на единицу. Как только значение позиции станет больше, чем длина строки, цикл будет завершен и вернет истину; в противном случае он вернет false.

Примеры техник поиска анаграмм на Python

Есть несколько методов и примеров, которые мы можем использовать для поиска анаграммы в Python. Эти методы приведены ниже.

1. Техника подсчета

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

Давайте разберем на примере.

from collections import Counter, defaultdict def checking_anagram(keywords): agrms = defaultdict(list) for i in keywords: hist = tuple(Counter(i).items()) agrms[hist].append(i) return list(agrms.values()) keywords =("python","yphotn") print(checking_anagram(keywords))

Мы импортировали модуль коллекции и его методы Count и defaultdict, чтобы проверить анаграмму строки в приведенном выше коде. Мы определили метод check_anagram() для подсчета и записи каждого символа с помощью функции счетчика. Каждый счет преобразуется в список и отслеживается. Этот процесс выполняется для всех символов в первой строке, кроме второй. Если количество обеих строк совпадает, это означает, что обе строки являются анаграммами.

2. Метод сортировки

В этом методе обе строки сортируются и проверяют, соответствуют ли оба значения друг другу. Давайте разберемся в следующем примере.

def Anogram_check(str1, str2): # Strings are sorted and check whether both are matching or not if(sorted(str1)== sorted(str2)): print("Both strings are an Anagram.") else: print("Both strings are not an Anagram.") string1 ="python" string2 ="ythopn" print( "String value1 : ", str1 ) print( "String value2 : ", str2 ) Anogram_check(string1, str2)

String value1 : python String value2 : ythopn Both strings are an Anagram.

В приведенном выше коде мы определили метод check_anagram() и передали две строки. В методе check_anagram() мы сохранили строку в определенных переменных. Мы сравнили каждую строку после сортировки. Если сравнение между строками совпало, данная строка формируется как анаграмма; в противном случае они вернулись как Обе строки не являются анаграммами. Этот метод относительно простой и эффективный. Это значительно снижает сложность кода.

3. Обратная проверка анаграммы

Мы можем применить эту технику следующим образом.

words_list = ["cat", "tac", "Play", "ay"] anagrams = <> for w in words_list: reverse_word=w[::-1] if reverse_word in words_list: anagrams[w] =(words_list.pop(words_list.index(reverse_word))) print(anagrams)

В приведенном выше коде мы использовали этот метод для сравнения анаграмм среди перевернутой строки. Здесь мы сформировали две разные строки. Этот метод похож на палиндромы, где мы перевернули одну строку и проверили ее с другими строками. Если они совпадают, струны образуют анаграмму; если они не совпадают, они не определяются как анаграммы.

4. Методика проверки положения

В этом методе уровень позиции сравнивается с проверкой анаграммы. Мы можем добиться этого, сверяя позиционный символ первой строки с каждой позиционной символьной строкой в другой строке. Если первая строка совпадает с другой строкой, она объявляется анаграммой.

def checking_anagram(str1,str2): chk_var = True if len(str1) != len(str2): chk_var = False list1 = list(str2) pos_string1 = 0 while pos_string1 < len(str1) and chk_var: pos_string2 = 0 found = False while pos_string2 < len(list1) and not found: if str1[pos_string1] == list1[pos_string2]: found = True else: pos_string2 = pos_string2 + 1 if found: list1[pos_string2] = None else: chk_var = False pos_string1 = pos_string1 + 1 return chk_var str1 = "ythopn" str2 = "python" print("String value1 : " , str1) print("String value2 : " , str2) Boolean_out = checking_anagram('ythopn','python') if Boolean_out: print( "Both words are Alogram " ) else: print( "Both words are not Alogram " )

String value1 : ythopn String value2 : python

В этом еще одна техника получения анаграммы двух строк. Здесь мы также использовали сравнение. Во вложенном цикле while мы передаем строку в эти циклы для процесса проверки.

Внешний цикл while используется для обработки одной из строк, а внутренний цикл – для другой строки. Символ одной строки сравнивается с другой строкой каждого символа, и этот процесс продолжается для каждой буквы в первой строке. Если все символы первой строки совпадают с другой строкой, то обе строки должны быть анаграммой. Этот метод – очень стабильный процесс, потому что он работает по алгоритму, точно оценивая строки.

Источник