Сегодня у нас маленькая приятная задачка на Python с собеседования в 📱. Погнали!
Написать функцию `anagram_check`, принимающую две строки и возвращающую True/False в зависимости от того, являются ли слова анаграммами.
➡️ Важно! Мы работаем с анаграммами
Анаграмма - это когда мы переставляем буквы в слове. АББА и ББАА - это анаграммы. АБ и АВ - не анаграммы. АБ и АБВ - не анаграммы.
Соответственно, вам нужно проверить, что количества символов каждого типа в двух строках совпадают 😎
Обычно неправильное понимание слова "анаграмма" генерит три типа ошибок. Кандидат:
1️⃣ Путает анаграмму и палиндром и делает не то
2️⃣ Не учитывает, что "абба" != "аб", проверяя только буквы, не их количество
3️⃣ Делает проверку только в одну сторону. Например, вам дали слова "абба" и "аббаззз", и вы проверяете, что буквы "абба" есть в "абабззз" и выдаете True, но не проверяете обратное направление.
Короче - сначала делаем базу. А именно разбираемся, что от нас хотят.
➡️ Важно х2! Мы работаем с текстом
Поэтому всегда надо уточнять у собеседующего, как мы обрабатываем знаки препинания и разный регистр.
Это сильно важнее в задачах на палиндром, здесь мы будем считать, что знаков препинания нет, и у нас одно слово в нижнем регистре.
Но если вдруг это не так:
s_old = 'AbBa!$'
punctuation = set("!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~")
s_new = "".join(char for char in s_old if char not in punctuation).lower()
s_new ## 'abba'
➡️ Как считать количество символов каждого типа?
Если вам дают пользоваться библиотеками, то это очевидный намек на Counter, и ваш код сведется к следующему:
from collections import Counter
def anagram_check(s: str, t: str) -> bool:
return Counter(s) == Counter(t)
Counter используется для быстрого подсчета количества элементов в коллекции (обычно список или строка). Он создает объект, напоминающий обычный словарь, где элементы выступают в роли ключей, а их количество - в роли значений.
К Counter, как и к словарю, кстати, можно применять .values(), .keys() и .items(), что довольно удобно.
➡️ А если нельзя пользоваться библиотеками?
Тогда логично проверять с помощью словаря 🥁 Давайте начнем с простого решения - мы просто сделаем Counter руками:
def anagram_check(s: str, t: str) -> bool:
counts_s = {}
counts_t = {}
for c in s:
counts_s[c] = counts_s.get(c, 0) + 1
for c in t:
counts_t[c] = counts_t.get(c, 0) + 1
return counts_s == counts_t
🚨 Научитесь использовать get! Это САМЫЙ удобный способ работать с ситуациями, когда ключа нет в словаре.
➡️ Более элегантное решение
Разберем более элегантный алгоритм:
def anagram_check(s: str, t: str) -> bool:
if len(s) != len(t):
return False ## сразу проверяете, что длина совпадает
counts = {}
for c in s:
counts[c] = counts.get(c, 0) + 1
for c in t:
counts[c] = counts.get(c, 0) - 1
if counts[c] < 0:
return False
return True
Что мы тут сделали?
1️⃣ Если длина не совпадает - не анаграммы
Мы это можем вставить в начало и нашего простого решения. Это просто порежет очень большой % случаев, когда у нас точно не анаграммы.
2️⃣ Мы создаем только один словарь!
Алгоритм такой:
• Проходимся по слову_1 и создаем Counter букв вручную (словарь counts)
• Проходимся по каждой букве в слове_2 и вычитаем единицу из каждого ключа в counts, соответствующего букве в слове_2
• Если хоть у одного ключа value < 0 - бинго! ✌️ Это не анаграмма
➡️ Почему это работает?
Если слова одной длины, но не анаграммы, то какой-то буквы во втором слове обязательно больше, чем в первом - на ней и вылезет минус 😉
3️⃣ В конце return True
Если длины равны и если ничего не ушло в минус, то все счетчики ровно нули - слова анаграммы.
————
Ну что, смогла вас где-то подловить? 🥁
Смотрите предыдущие разборы!
• Разбор задачек с собеседований vol. 3
• Разбор задачек с собеседований vol. 4
• Разбор задачек с собеседований vol. 5