Анаграммы (Valid Anagram): Разбор задачи для начинающих

Почему эту задачу часто дают на собеседованиях?

Задача с анаграммами — это не просто проверка работы со строками. Она показывает, как вы:

• Работаете с базовыми структурами данных
• Оптимизируете использование памяти
• Обрабатываете различные краевые случаи
• Понимаете trade-offs разных решений

Давайте разберем задачу по шагам

Что нужно сделать?

У вас есть две строки. Нужно определить, являются ли они анаграммами друг друга. Анаграмма — это когда две строки состоят из одинаковых символов в разном порядке.

Например:

const s = 'listen'
const t = 'silent'

// Нужно вернуть true, потому что строки содержат одни и те же буквы

Решение 1: Самое простое (через сортировку)

Давайте подумаем, как бы мы решили эту задачу в реальной жизни:

1. Отсортируем буквы в обеих строках
2. Сравним получившиеся строки
3. Если они одинаковые — это анаграммы

function areAnagramsSimple(s, t) {
  if (s.length !== t.length) {
    return false
  }

  const sortedS = s.split('').sort().join('')
  const sortedT = t.split('').sort().join('')

  return sortedS === sortedT
}

Это работает! Но не самый эффективный способ.

Решение 2: Умное решение (через хеш-таблицу)

Давайте подумаем хитрее:

• Можно посчитать количество каждой буквы в первой строке
• Затем вычесть количество букв из второй строки
• Если все счетчики станут нулями — это анаграммы

function areAnagramsSmart(s, t) {
  if (s.length !== t.length) {
    return false
  }

  const charCount = {}

  // Считаем символы первой строки
  for (let char of s) {
    charCount[char] = (charCount[char] || 0) + 1
  }

  // Вычитаем символы второй строки
  for (let char of t) {
    if (!charCount[char]) {
      return false
    }
    charCount[char]--
  }

  // Проверяем, что все счетчики равны 0
  return Object.values(charCount).every((count) => count === 0)
}

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→

Почему второе решение лучше?

1. 🚀 Скорость:

   • Первое решение: требует сортировки (O(n log n))
   • Второе решение: один проход по каждой строке (O(n))

2. 📝 Память:

   • Первое решение: создает новые строки (O(n))
   • Второе решение: хранит только счетчики символов (O(1) для ASCII)

Советы для собеседования

1. Начните с простого

   • Покажите решение через сортировку
   • Объясните, почему оно не оптимально

2. Предложите улучшения

   • Расскажите про решение со счетчиками
   • Объясните выигрыш в производительности

3. Обсудите особые случаи

   • Пустые строки
   • Регистр букв
   • Unicode символы

Дополнительные вопросы для размышления

1. Как оптимизировать для ASCII строк?

function areAnagramsASCII(s, t) {
  if (s.length !== t.length) return false

  const counts = new Array(128).fill(0)

  for (let i = 0; i < s.length; i++) {
    counts[s.charCodeAt(i)]++
    counts[t.charCodeAt(i)]--
  }

  return counts.every((count) => count === 0)
}

1. Как найти все анаграммы в массиве строк?

function groupAnagrams(words) {
  const groups = {}

  for (let word of words) {
    const key = word.split('').sort().join('')
    if (!groups[key]) {
      groups[key] = []
    }
    groups[key].push(word)
  }

  return Object.values(groups)
}

1. Как обрабатывать Unicode?

function areAnagramsUnicode(s, t) {
  // Нормализация строк для корректной работы с Unicode
  s = s.normalize('NFD')
  t = t.normalize('NFD')
  return areAnagramsSmart(s, t)
}

Заключение

Задача с анаграммами — отличный пример того, как простая на первый взгляд задача может научить важным концепциям:

• Работе со строками и символами
• Использованию хеш-таблиц
• Оптимизации памяти и времени выполнения
• Обработке краевых случаев

Главное — не просто запомнить решение, а понять принципы оптимизации и почему мы используем определенные подходы.