Подготовка к алгоритмическим задачам

Правильный палиндром: разбор задачи

8 мин чтения

алгоритмы

строки

оптимизация

Почему эта задача важна?

Задача на проверку палиндрома позволяет оценить:

🧠 Умение работать со строками и их обработкой
⚡ Навыки оптимизации решений
🎯 Понимание регулярных выражений и фильтрации символов
🐛 Способность обрабатывать краевые случаи

Постановка задачи

Формулировка:

Дана строка s. Верните true, если она является палиндромом, и false в противном случае. Палиндром - это строка, которая читается одинаково слева направо и справа налево. При этом регистр букв не имеет значения, а все символы, не являющиеся буквами или цифрами, игнорируются.

Примеры:

// Первый пример ✅
Input: s = "Was it a car or a cat I saw?"
Output: true
Объяснение: После удаления пробелов и приведения к нижнему регистру получаем "wasitacaroracatisaw", 
что является палиндромом.

// Второй пример ❌
Input: s = "race a car"
Output: false
Объяснение: После обработки получаем "raceacar", что не является палиндромом.

Подходы к решению

Решение 1: Двойной указатель (двухуказательный подход)

function isPalindrome(s) {
  // Приводим к нижнему регистру и удаляем все не буквенно-цифровые символы
  s = s.toLowerCase().replace(/[^a-z0-9]/g, '');
  
  let left = 0;
  let right = s.length - 1;
  
  while (left < right) {
    if (s[left] !== s[right]) {
      return false;
    }
    left++;
    right--;
  }
  
  return true;
}

Анализ решения:

✅ Эффективная временная сложность O(n)

✅ Простая и понятная реализация

✅ Минимальное использование дополнительной памяти O(1) (не считая преобразования строки)

❌ Требует предварительной обработки строки

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

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

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

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

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

Решение 2: Создание и сравнение обратной строки 🔄

function isPalindrome(s) {
  // Приводим к нижнему регистру и удаляем все не буквенно-цифровые символы
  s = s.toLowerCase().replace(/[^a-z0-9]/g, '');
  
  // Переворачиваем строку и сравниваем с исходной
  const reversed = s.split('').reverse().join('');
  
  return s === reversed;
}

Характеристики:

✅ Очень простая и читаемая реализация

✅ Легко понять логику решения

❌ Требует дополнительной памяти O(n)

❌ Создает дополнительные копии строки

Решение 3: Без регулярных выражений (ручная фильтрация) 🧹

function isPalindrome(s) {
  let filtered = '';
  
  // Вручную фильтруем строку
  for (const char of s) {
    if (isAlphanumeric(char)) {
      filtered += char.toLowerCase();
    }
  }
  
  // Проверяем, является ли результат палиндромом
  let left = 0;
  let right = filtered.length - 1;
  
  while (left < right) {
    if (filtered[left] !== filtered[right]) {
      return false;
    }
    left++;
    right--;
  }
  
  return true;
}

function isAlphanumeric(char) {
  const code = char.charCodeAt(0);
  return (
    (code >= 48 && code <= 57) || // цифры
    (code >= 65 && code <= 90) || // заглавные буквы
    (code >= 97 && code <= 122)   // строчные буквы
  );
}

Преимущества и недостатки:

✅ Не использует регулярные выражения (может быть важно в некоторых средах)

✅ Более явный контроль над процессом фильтрации

❌ Более многословный код

❌ Требует дополнительной памяти O(n)

Решение 4: Оптимизированный двойной указатель (без промежуточной строки) 🚀

function isPalindrome(s) {
  let left = 0;
  let right = s.length - 1;
  
  while (left < right) {
    // Пропускаем не буквенно-цифровые символы слева
    while (left < right && !isAlphanumeric(s[left])) {
      left++;
    }
    
    // Пропускаем не буквенно-цифровые символы справа
    while (left < right && !isAlphanumeric(s[right])) {
      right--;
    }
    
    // Сравниваем символы без учета регистра
    if (s[left].toLowerCase() !== s[right].toLowerCase()) {
      return false;
    }
    
    left++;
    right--;
  }
  
  return true;
}

function isAlphanumeric(char) {
  const code = char.charCodeAt(0);
  return (
    (code >= 48 && code <= 57) || // цифры
    (code >= 65 && code <= 90) || // заглавные буквы
    (code >= 97 && code <= 122)   // строчные буквы
  );
}

Особенности:

✅ Оптимальная временная сложность O(n)

✅ Не требует дополнительной памяти для хранения обработанной строки

✅ Обработка происходит на лету, без предварительного преобразования

❌ Более сложная логика, требующая внимательной реализации

Распространённые ошибки

🤦‍♂️ Забывание привести символы к одному регистру перед сравнением
😅 Неправильная обработка специальных символов и пробелов
🐌 Использование избыточных преобразований строки

Оптимизации

Оптимизация для коротких строк

function isPalindrome(s) {
  // Для коротких строк можно использовать простой подход
  if (s.length <= 1) return true;
  
  s = s.toLowerCase().replace(/[^a-z0-9]/g, '');
  return s === s.split('').reverse().join('');
}

Эффективная проверка с ранним выходом

function isPalindrome(s) {
  // Быстрая проверка для пустых строк
  if (s.length === 0) return true;
  
  s = s.toLowerCase().replace(/[^a-z0-9]/g, '');
  
  // Быстрая проверка для строк длиной 1
  if (s.length <= 1) return true;
  
  // Быстрая проверка первого и последнего символа
  if (s[0] !== s[s.length - 1]) return false;
  
  // Полная проверка
  let left = 0;
  let right = s.length - 1;
  
  while (left < right) {
    if (s[left] !== s[right]) {
      return false;
    }
    left++;
    right--;
  }
  
  return true;
}

Заключение

При решении задачи важно помнить:

🤹‍♂️ Существует несколько подходов с разным балансом простоты и эффективности
📊 Предварительная обработка строки упрощает решение, но требует дополнительной памяти
🧠 Непосредственная проверка с двумя указателями является наиболее оптимальной

Эта задача отлично демонстрирует различные техники работы со строками и важность учета особых условий в алгоритмических задачах. 🌟

Попробуй решить популярные задачи

Массивы и Хеширование