Как реализовать проверку анаграмм для двух строк

Пошаговый план реализации проверки анаграмм

1. Проверка длины строк: Если строки разной длины, они не могут быть анаграммами.
2. Сортировка строк: Сортируем обе строки и сравниваем их. Если отсортированные строки равны, это анаграммы.
3. Использование хэш-таблицы: Создаем частотный словарь символов для одной строки и уменьшаем счетчик для символов из второй строки. Если все значения равны нулю, это анаграммы.

Пример реализации на Python

def are_anagrams(str1, str2):
    # Проверка длины строк
    if len(str1) != len(str2):
        return False  # Разные длины - не анаграммы

    # Сортировка строк и сравнение
    if sorted(str1) == sorted(str2):
        return True  # Строки равны после сортировки, это анаграммы

    # Использование хэш-таблицы для проверки
    char_count = {}
    
    for char in str1:
        char_count[char] = char_count.get(char, 0) + 1  # Увеличиваем счетчик символа

    for char in str2:
        if char in char_count:
            char_count[char] -= 1  # Уменьшаем счетчик символа
        else:
            return False  # Символ отсутствует в первой строке

    # Если все значения в словаре равны нулю, это анаграммы
    return all(count == 0 for count in char_count.values())

# Тестирование функции
print(are_anagrams('listen', 'silent'))  # True
print(are_anagrams('hello', 'world'))    # False
print(are_anagrams('triangle', 'integral'))  # True
print(are_anagrams('night', 'thing'))     # True
print(are_anagrams('abc', 'cba'))         # True

Примечания по коду

• Проверка длины: Первое условие предотвращает лишние операции для строк разной длины.
• Сортировка: Простое решение, но менее оптимальное по времени (O(n log n)).
• Хэш-таблица: Оптимальное решение с временной сложностью O(n), что лучше для больших строк.