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

Решение

Анаграмма — это слово или фраза, составленная из букв другого слова/фразы в другом порядке. Разберу несколько подходов.

Подход 1: Сортировка символов

function isAnagram(str1: string, str2: string): boolean {
  // Очищаем строки, переводим в нижний регистр
  const normalize = (str: string) => 
    str.toLowerCase().replace(/[^a-z0-9]/g, "");
  
  const clean1 = normalize(str1);
  const clean2 = normalize(str2);
  
  // Сортируем символы и сравниваем
  return clean1.split("").sort().join("") === clean2.split("").sort().join("");
}

Как работает:

1. Нормализуем обе строки (нижний регистр, удаляем пробелы/знаки)
2. Разбиваем на символы .split("")
3. Сортируем .sort()
4. Объединяем .join("")
5. Сравниваем результаты

Временная сложность: O(n log n) из-за сортировки Пространственная сложность: O(n)

Подход 2: Подсчёт символов (оптимально)

function isAnagram(str1: string, str2: string): boolean {
  const normalize = (str: string) => 
    str.toLowerCase().replace(/[^a-z0-9]/g, "");
  
  const clean1 = normalize(str1);
  const clean2 = normalize(str2);
  
  // Если длины разные — не анаграмма
  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 true;
}

Преимущества:

• Временная сложность: O(n) — линейная
• Пространственная сложность: O(k) где k = количество уникальных символов
• Ранний выход, если длины не совпадают
• Более эффективна на больших строках

Подход 3: С использованием Map

function isAnagram(str1: string, str2: string): boolean {
  const normalize = (str: string) => 
    str.toLowerCase().replace(/[^a-z0-9]/g, "");
  
  const clean1 = normalize(str1);
  const clean2 = normalize(str2);
  
  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;
    }
    const count = charMap.get(char)!;
    if (count === 1) {
      charMap.delete(char);
    } else {
      charMap.set(char, count - 1);
    }
  }
  
  return charMap.size === 0;
}

Подход 4: Функциональный с reduce

function isAnagram(str1: string, str2: string): boolean {
  const normalize = (str: string) => 
    str.toLowerCase().replace(/[^a-z0-9]/g, "");
  
  const clean1 = normalize(str1);
  const clean2 = normalize(str2);
  
  if (clean1.length !== clean2.length) {
    return false;
  }
  
  const countChars = (str: string) =>
    [...str].reduce((acc, char) => {
      acc[char] = (acc[char] || 0) + 1;
      return acc;
    }, {} as Record<string, number>);
  
  const count1 = countChars(clean1);
  const count2 = countChars(clean2);
  
  return JSON.stringify(count1) === JSON.stringify(count2);
}

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

console.log(isAnagram("listen", "silent"));              // true
console.log(isAnagram("hello", "world"));               // false
console.log(isAnagram("Dormitory", "dirty room"));      // true
console.log(isAnagram("The Eyes", "They See"));         // true
console.log(isAnagram("a", "a"));                       // true
console.log(isAnagram("ab", "ba"));                     // true
console.log(isAnagram("", ""));                         // true
console.log(isAnagram("abc", "def"));                   // false
console.log(isAnagram("aab", "abb"));                   // false

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

Рекомендация для интервью

Начните с подхода сортировки (простая и понятная), затем упомяните, что в production используете подход подсчёта символов для лучшей производительности на больших данных.

Ключевые моменты:

• Нормализация важна: нижний регистр, удаление пробелов
• Если длины разные — сразу false
• Подсчёт символов быстрее сортировки на больших объёмах
• Регулярное выражение [^a-z0-9] удаляет всё кроме букв и цифр