Проверка двух строк на анаграмму

Решение

Задача на проверку анаграмм — проверяет понимание структур данных и алгоритмов сортировки. Это часто встречается на собеседованиях, так как показывает знание оптимизации.

Решение 1: Сортировка

Самый интуитивный подход — отсортировать буквы и сравнить:

function isAnagram(str1: string, str2: string): boolean {
  // Очищаем строки: удаляем пробелы, приводим к нижнему регистру
  const clean1 = str1.toLowerCase().replace(/\s/g, "");
  const clean2 = str2.toLowerCase().replace(/\s/g, "");
  
  // Проверяем длину
  if (clean1.length !== clean2.length) {
    return false;
  }
  
  // Сортируем буквы и сравниваем
  const sorted1 = clean1.split("").sort().join("");
  const sorted2 = clean2.split("").sort().join("");
  
  return sorted1 === sorted2;
}

Анализ:

• Временная сложность: O(n log n) из-за сортировки
• Пространственная сложность: O(n) для новых строк
• Простота: высокая, код читаемый

Решение 2: Подсчёт частоты (оптимальное)

Более эффективный подход — подсчитать частоту каждого символа:

function isAnagramOptimal(str1: string, str2: string): boolean {
  // Очищаем строки
  const clean1 = str1.toLowerCase().replace(/\s/g, "");
  const clean2 = str2.toLowerCase().replace(/\s/g, "");
  
  // Проверяем длину
  if (clean1.length !== clean2.length) {
    return false;
  }
  
  // Создаём объект для подсчёта букв
  const charCount: Record<string, number> = {};
  
  // Считаем буквы первой строки
  for (const char of clean1) {
    charCount[char] = (charCount[char] || 0) + 1;
  }
  
  // Вычитаем буквы второй строки
  for (const char of clean2) {
    if (!charCount[char]) {
      return false; // Буква не найдена или уже использована
    }
    charCount[char]--;
  }
  
  // Проверяем, что все буквы использованы
  return Object.values(charCount).every(count => count === 0);
}

Анализ:

• Временная сложность: O(n) — два прохода по строке
• Пространственная сложность: O(1) для англиского алфавита (максимум 26 букв)
• Эффективность: лучше для больших строк

Решение 3: Использование Map

Можно использовать Map для более современного подхода:

function isAnagramMap(str1: string, str2: string): boolean {
  const clean1 = str1.toLowerCase().replace(/\s/g, "");
  const clean2 = str2.toLowerCase().replace(/\s/g, "");
  
  if (clean1.length !== clean2.length) return false;
  
  const charMap = new Map<string, number>();
  
  for (const char of clean1) {
    charMap.set(char, (charMap.get(char) || 0) + 1);
  }
  
  for (const char of clean2) {
    if (!charMap.has(char)) return false;
    charMap.set(char, charMap.get(char)! - 1);
    if (charMap.get(char) === 0) charMap.delete(char);
  }
  
  return charMap.size === 0;
}

Примеры использования

console.log(isAnagram("listen", "silent"));           // true
console.log(isAnagram("finder", "Friend"));           // true
console.log(isAnagram("hello", "world"));             // false
console.log(isAnagram("Dormitory", "dirty room"));   // true
console.log(isAnagram("a", "a"));                     // true
console.log(isAnagram("ab", "ba"));                   // true

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

Рекомендации для собеседования

1. Начните с сортировки — просто и быстро реализуется
2. Потом предложите оптимизацию — покажите знание алгоритмов
3. Обсудите граничные случаи — пустые строки, одна буква
4. Объясните трейд-офф — O(n) время vs O(1) память
5. Упомяните регулярные выражения — для очистки строк

Для реального проекта выбирайте подход с подсчётом (O(n)) — это оптимальное соотношение скорости и простоты.