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

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

Анаграмма — это слово, образованное перестановкой букв другого слова. Например, "listen" и "silent" — анаграммы, так как содержат одинаковые буквы в разном порядке.

Основной подход: сортировка букв

Если две строки содержат одинаковые буквы с одинаковой частотой, то они анаграммы.

def is_anagram(str1, str2):
    # Убираем пробелы, преобразуем в нижний регистр
    str1_cleaned = str1.replace(" ", "").lower()
    str2_cleaned = str2.replace(" ", "").lower()
    
    # Если отсортированные строки совпадают, это анаграмма
    return sorted(str1_cleaned) == sorted(str2_cleaned)

# Тестирование
print(is_anagram("listen", "silent"))  # True
print(is_anagram("hello", "world"))    # False
print(is_anagram("restful", "fluster")) # True
print(is_anagram("The Eyes", "They See"))  # True

Объяснение

# Пример для "listen" и "silent"
str1 = "listen"
str2 = "silent"

str1_sorted = sorted(str1)  # ['e', 'i', 'l', 'n', 's', 't']
str2_sorted = sorted(str2)  # ['e', 'i', 'l', 'n', 's', 't']

print(str1_sorted == str2_sorted)  # True — анаграмма!

Альтернатива: подсчёт частоты букв (Counter)

Более явный и читаемый подход:

from collections import Counter

def is_anagram(str1, str2):
    # Убираем пробелы, преобразуем в нижний регистр
    str1_cleaned = str1.replace(" ", "").lower()
    str2_cleaned = str2.replace(" ", "").lower()
    
    # Counter создаёт словарь {буква: количество}
    return Counter(str1_cleaned) == Counter(str2_cleaned)

# Тестирование
print(is_anagram("listen", "silent"))  # True
print(is_anagram("hello", "world"))    # False
print(is_anagram("restful", "fluster")) # True

# Как работает Counter
counter1 = Counter("listen")
print(counter1)  # Counter({'s': 1, 't': 1, 'l': 1, 'i': 1, 'e': 1, 'n': 1})

counter2 = Counter("silent")
print(counter2)  # Counter({'s': 1, 'i': 1, 'l': 1, 'e': 1, 'n': 1, 't': 1})

print(counter1 == counter2)  # True

Ручной подсчёт букв (без импортов)

def is_anagram(str1, str2):
    str1_cleaned = str1.replace(" ", "").lower()
    str2_cleaned = str2.replace(" ", "").lower()
    
    # Если длины разные, не анаграмма
    if len(str1_cleaned) != len(str2_cleaned):
        return False
    
    # Создаём словарь частот букв
    char_count = {}
    
    # Подсчитываем буквы из первой строки
    for char in str1_cleaned:
        char_count[char] = char_count.get(char, 0) + 1
    
    # Проверяем вторую строку
    for char in str2_cleaned:
        if char not in char_count:
            return False
        char_count[char] -= 1
        if char_count[char] < 0:
            return False
    
    # Все буквы учтены
    return all(count == 0 for count in char_count.values())

# Тестирование
print(is_anagram("listen", "silent"))  # True
print(is_anagram("hello", "world"))    # False

Сравнение подходов

1. Сортировка (самый простой)

return sorted(str1_cleaned) == sorted(str2_cleaned)
# Плюсы: компактно, просто
# Минусы: O(n log n) временная сложность

2. Counter (самый читаемый)

return Counter(str1_cleaned) == Counter(str2_cleaned)
# Плюсы: явно показывает намерение, O(n)
# Минусы: нужен импорт, создание нескольких объектов

3. Ручной подсчёт (самый эффективный)

# Ручная реализация
# Плюсы: O(n), понимаем внутренности
# Минусы: больше кода, более сложно

С валидацией и обработкой особых случаев

from collections import Counter

def is_anagram(str1, str2):
    """
    Проверяет, являются ли две строки анаграммами.
    
    Args:
        str1: первая строка
        str2: вторая строка
    
    Returns:
        True, если анаграмма; False иначе
    
    Примеры:
        is_anagram('listen', 'silent') -> True
        is_anagram('hello', 'world') -> False
    """
    if not isinstance(str1, str) or not isinstance(str2, str):
        raise TypeError("Аргументы должны быть строками")
    
    # Нормализация: удаляем пробелы и приводим к нижнему регистру
    str1_cleaned = str1.replace(" ", "").lower()
    str2_cleaned = str2.replace(" ", "").lower()
    
    # Пустые строки — анаграммы друг друга
    if not str1_cleaned and not str2_cleaned:
        return True
    
    # Одна из строк пуста
    if len(str1_cleaned) != len(str2_cleaned):
        return False
    
    # Сравниваем Counter
    return Counter(str1_cleaned) == Counter(str2_cleaned)

# Тестирование
print(is_anagram("listen", "silent"))  # True
print(is_anagram("The Eyes", "They See"))  # True
print(is_anagram("hello", "world"))    # False
print(is_anagram("", ""))  # True
print(is_anagram("a", "a"))  # True
print(is_anagram("ab", "ba"))  # True

Учёт пунктуации и спецсимволов

import re
from collections import Counter

def is_anagram(str1, str2):
    # Удаляем всё кроме букв (буквы и пробелы)
    str1_cleaned = re.sub(r'[^a-z ]', '', str1.lower())
    str2_cleaned = re.sub(r'[^a-z ]', '', str2.lower())
    
    # Удаляем пробелы
    str1_cleaned = str1_cleaned.replace(" ", "")
    str2_cleaned = str2_cleaned.replace(" ", "")
    
    return Counter(str1_cleaned) == Counter(str2_cleaned)

# Примеры
print(is_anagram("Listen!", "Silent?"))  # True
print(is_anagram("abc-123", "cba"))  # True

Юнит-тесты

from collections import Counter

def is_anagram(str1, str2):
    str1_cleaned = str1.replace(" ", "").lower()
    str2_cleaned = str2.replace(" ", "").lower()
    return Counter(str1_cleaned) == Counter(str2_cleaned)

# Тесты
assert is_anagram("listen", "silent") == True
assert is_anagram("hello", "world") == False
assert is_anagram("restful", "fluster") == True
assert is_anagram("The Eyes", "They See") == True
assert is_anagram("", "") == True
assert is_anagram("a", "b") == False
assert is_anagram("abc", "cba") == True

print("Все тесты пройдены!")

Временная и пространственная сложность

Рекомендация: для большинства случаев используйте Counter — самый читаемый и эффективный вариант.