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

Решение: Проверка анаграмм

Описание задачи

Требуется реализовать функцию для определения, являются ли две строки анаграммами (anagrams) друг друга. Анаграмма — это слово или фраза, составленная из тех же букв, что и исходное слово, но в другом порядке. При проверке необходимо игнорировать регистр букв, пробелы и знаки препинания. Эта задача часто встречается в тестировании обработки текстовых данных, валидации пользовательского ввода и работе со строками в автоматизированном тестировании.

Решение на Python

def are_anagrams(str1, str2):
    """
    Проверяет, являются ли две строки анаграммами.
    
    Args:
        str1: первая строка
        str2: вторая строка
    
    Returns:
        True, если строки анаграммы, False иначе
    """
    import re
    
    # Удаляем всё кроме букв и цифр, приводим к нижнему регистру
    def clean_string(s):
        return ''.join(re.findall(r'[a-z0-9]', s.lower()))
    
    # Очищаем обе строки
    cleaned1 = clean_string(str1)
    cleaned2 = clean_string(str2)
    
    # Сортируем символы и сравниваем
    return sorted(cleaned1) == sorted(cleaned2)

Альтернативные подходы

1. Использование Counter из collections

from collections import Counter
import re

def are_anagrams_counter(str1, str2):
    """
    Использует Counter для подсчёта частоты символов.
    Более эффективно для больших строк.
    """
    def clean_string(s):
        return ''.join(re.findall(r'[a-z0-9]', s.lower()))
    
    cleaned1 = clean_string(str1)
    cleaned2 = clean_string(str2)
    
    return Counter(cleaned1) == Counter(cleaned2)

2. С явной проверкой длины

def are_anagrams_optimized(str1, str2):
    """
    Оптимизированный вариант с ранней проверкой длины.
    """
    import re
    
    def clean_string(s):
        return ''.join(re.findall(r'[a-z0-9]', s.lower()))
    
    cleaned1 = clean_string(str1)
    cleaned2 = clean_string(str2)
    
    # Если длины разные, то не анаграммы
    if len(cleaned1) != len(cleaned2):
        return False
    
    return sorted(cleaned1) == sorted(cleaned2)

3. С подсчётом частоты символов (вручную)

def are_anagrams_manual(str1, str2):
    """
    Ручной подсчёт частоты символов без использования Counter.
    """
    import re
    
    def clean_string(s):
        return ''.join(re.findall(r'[a-z0-9]', s.lower()))
    
    cleaned1 = clean_string(str1)
    cleaned2 = clean_string(str2)
    
    if len(cleaned1) != len(cleaned2):
        return False
    
    # Подсчитываем частоту символов
    freq = {}
    
    for char in cleaned1:
        freq[char] = freq.get(char, 0) + 1
    
    for char in cleaned2:
        if char not in freq:
            return False
        freq[char] -= 1
        if freq[char] < 0:
            return False
    
    return True

4. С использованием только встроенных функций

def are_anagrams_builtin(str1, str2):
    """
    Использует только встроенные функции и не требует импортов (кроме re).
    """
    import re
    
    # Очищаем строки от всего кроме букв и цифр
    chars1 = sorted(re.sub(r'[^a-z0-9]', '', str1.lower()))
    chars2 = sorted(re.sub(r'[^a-z0-9]', '', str2.lower()))
    
    return chars1 == chars2

Тестовые примеры

import unittest

class TestAreAnagrams(unittest.TestCase):
    
    def test_basic_anagrams(self):
        # Базовый случай из условия
        assert are_anagrams('listen', 'silent') == True
    
    def test_not_anagrams(self):
        # Не анаграммы из условия
        assert are_anagrams('hello', 'world') == False
    
    def test_empty_strings(self):
        # Пустые строки — анаграммы
        assert are_anagrams('', '') == True
    
    def test_single_char(self):
        # Одиночный символ
        assert are_anagrams('a', 'a') == True
    
    def test_case_insensitive(self):
        # Игнорирование регистра
        assert are_anagrams('Listen', 'SILENT') == True
    
    def test_with_spaces(self):
        # С пробелами
        assert are_anagrams('the eyes', 'they see') == True
    
    def test_with_punctuation(self):
        # Со знаками препинания
        assert are_anagrams('Dormitory,', 'dirty room.') == True
    
    def test_with_numbers(self):
        # С цифрами
        assert are_anagrams('abc123', '321cba') == True
    
    def test_different_lengths(self):
        # Разные длины (после очистки)
        assert are_anagrams('abcd', 'abc') == False
    
    def test_repeated_chars(self):
        # С повторяющимися символами
        assert are_anagrams('aab', 'aba') == True
    
    def test_repeated_chars_mismatch(self):
        # Разное количество одинаковых символов
        assert are_anagrams('aab', 'aa') == False
    
    def test_long_anagrams(self):
        # Длинные строки
        assert are_anagrams('a gentleman', 'elegant man') == True

Анализ сложности

Применение в QA Automation

• Тестирование обработки текста — проверка алгоритмов работы со строками
• Валидация пользовательского ввода — проверка, не вводит ли пользователь анаграммы вместо специального ввода
• Генерация тестовых данных — автоматическое создание анаграмм для покрытия edge cases
• Проверка безопасности — поиск подозрительных паттернов в пользовательском вводе
• Функциональное тестирование — проверка корректности словарных операций

Рекомендация

Для стандартного использования в QA рекомендуется подход с Counter — он обеспечивает оптимальную временную сложность O(n) и хорошо читаемый код. Для интервью и демонстрации понимания алгоритмов используйте ручной подсчёт частоты, так как он показывает глубокое понимание проблемы.