Как решить задачу является ли строка анаграммой другой строки?

Решение задачи проверки строк на анаграммы

Анаграмма — это слово или фраза, образованная перестановкой букв другого слова или фразы, с использованием всех исходных букв ровно один раз. Классические примеры: "listen" и "silent", "апельсин" и "спаниель".

Ключевые аспекты задачи

1. Регистр букв: Обычно проверка нечувствительна к регистру ("А" и "а" считаются одинаковыми)
2. Пробелы и знаки препинания: В зависимости от формулировки, могут игнорироваться или учитываться
3. Сложность алгоритма: Стремимся к оптимальному решению O(n)
4. Память: Используем дополнительную память для хранения счетчиков

Основные подходы к решению

1. Сортировка символов (Простейший, но не самый эффективный)

fun isAnagramSorting(str1: String, str2: String): Boolean {
    val s1 = str1.toLowerCase().replace("\\s".toRegex(), "")
    val s2 = str2.toLowerCase().replace("\\s".toRegex(), "")
    
    if (s1.length != s2.length) return false
    
    return s1.toCharArray().sorted() == s2.toCharArray().sorted()
}

Сложность: O(n log n) из-за сортировки, где n — длина строки
Плюсы: Простота реализации, читаемость кода
Минусы: Неоптимальная производительность для длинных строк

2. Подсчет символов с использованием HashMap (Универсальный подход)

fun isAnagramHashMap(str1: String, str2: String): Boolean {
    val s1 = str1.toLowerCase().filter { it.isLetterOrDigit() }
    val s2 = str2.toLowerCase().filter { it.isLetterOrDigit() }
    
    if (s1.length != s2.length) return false
    
    val charCount = mutableMapOf<Char, Int>()
    
    // Увеличиваем счетчики для первой строки
    for (char in s1) {
        charCount[char] = charCount.getOrDefault(char, 0) + 1
    }
    
    // Уменьшаем счетчики для второй строки
    for (char in s2) {
        val count = charCount[char] ?: return false
        if (count == 1) {
            charCount.remove(char)
        } else {
            charCount[char] = count - 1
        }
    }
    
    return charCount.isEmpty()
}

Сложность: O(n) по времени, O(k) по памяти (k — количество уникальных символов)
Плюсы: Работает с Unicode, гибкая обработка символов
Минусы: Накладные расходы на работу с HashMap

3. Подсчет символов с использованием массива (Оптимальный для ASCII)

fun isAnagramArray(str1: String, str2: String): Boolean {
    val s1 = str1.toLowerCase().filter { it.isLetterOrDigit() }
    val s2 = str2.toLowerCase().filter { it.isLetterOrDigit() }
    
    if (s1.length != s2.length) return false
    
    // Для ASCII символов достаточно 256, для расширенного ASCII — 65536
    val charCount = IntArray(256)
    
    for (i in s1.indices) {
        charCount[s1[i].toInt()]++
        charCount[s2[i].toInt()]--
    }
    
    // Проверяем, все ли счетчики равны нулю
    return charCount.all { it == 0 }
}

Сложность: O(n) по времени, O(1) по памяти (фиксированный размер массива)
Плюсы: Максимальная производительность, минимальные накладные расходы
Минусы: Работает только с ограниченным набором символов (ASCII)

Оптимизации и дополнительные соображения

Ранние проверки:

// Быстрая проверка перед основным алгоритмом
if (str1.length != str2.length) return false
if (str1 == str2) return true // если строки идентичны

Многопоточная обработка для очень длинных строк:

fun isAnagramParallel(str1: String, str2: String): Boolean {
    // Разделяем строки на части и обрабатываем в разных потоках
    // Объединяем результаты частных подсчетов
}

Тестирование решения

fun testAnagramFunctions() {
    val testCases = listOf(
        Triple("listen", "silent", true),
        Triple("Hello", "World", false),
        Triple("Апельсин", "Спаниель", true),
        Triple("", "", true),
        Triple("aacc", "ccac", false) // Важный краевой случай
    )
    
    testCases.forEach { (str1, str2, expected) ->
        val result = isAnagramArray(str1, str2)
        println("$str1 vs $str2: $result (expected: $expected)")
        assert(result == expected)
    }
}

Выбор подхода на собеседовании

1. Сначала упомянуть простое решение через сортировку — показываем понимание базового подхода
2. Предложить оптимизированное решение с подсчетом символов — демонстрируем знание алгоритмической оптимизации
3. Обсудить ограничения каждого подхода:
   • Сортировка: неэффективна для длинных строк
   • HashMap: универсален, но имеет накладные расходы
   • Массив: максимально эффективен, но только для ASCII
4. Уточнить требования к задаче:
   • Учитывать ли регистр?
   • Игнорировать ли пробелы и знаки препинания?
   • Каков ожидаемый размер входных данных?

Практическое применение в Android

В Android-разработке подобные алгоритмы могут применяться для:

• Поиска похожих слов в словарях и приложениях для изучения языков
• Проверки вводимых пользователем данных
• Игровой логики в word-играх
• Анализа текстового контента

Итоговый рекомендация: Для собеседования лучше всего реализовать решение с использованием массива счетчиков, предварительно обсудив допущения о кодировке символов, и обязательно покрыть код тестами для краевых случаев.