Анаграмма — это слово или словосочетание, образованное перестановкой букв другого слова или словосочетания. Например:

  • "кот" и "ток"

  • "апельсин" и "спаниель"

  • "лесопромышленность" и "солепромышленность"

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

Основные подходы к обнаружению анаграмм

 Метод сортировки символов

Самый простой и интуитивно понятный способ:

  1. Привести все символы в словах к одному регистру (обычно нижнему)

  2. Отсортировать символы в каждом слове по алфавиту

  3. Сравнить полученные отсортированные строки

def is_anagram(word1, word2):
    return sorted(word1.replace(' ', '').lower()) == sorted(word2.replace(' ', '').lower())

print(is_anagram('r ot', 'to r'))

Сложность: O(n log n) из-за операции сортировки

 Метод подсчёта символов

Более оптимальный подход с использованием хеш-таблиц для подсчёта символов:

  1. Создать словарь для подсчёта частот символов

  2. Увеличить счётчики для первого слова

  3. Уменьшить счётчики для второго слова

  4. Проверить, что все счётчики равны нулю

 

from collections import defaultdict

def is_anagram(word1, word2):
    if len(word1) != len(word2):
        return False
    
    counts = defaultdict(int)
    
    for char in word1.lower():
        counts[char] += 1
    
    for char in word2.lower():
        counts[char] -= 1
        if counts[char] < 0:
            return False
    
    return True

Сложность: O(n), но требует дополнительной памяти для хранения счётчиков