Проверка, является ли строка палиндромом

Перемешанные символы на тёмном фоне

Палиндром — это строка, совпадающая со своей обратной копией. В этой статье объяснён алгоритм проверки палиндрома и приведены реализации на C++, Python, C и JavaScript. Также рассмотрены альтернативные подходы, критерии приёмки, распространённые ошибки и полезные подсказки.

Что такое палиндром

Палиндром — строка, равная своей реверсированной версии. Пример: “racecar” и “madam”. Однострочное определение: палиндром — последовательность символов, читающаяся одинаково в обоих направлениях.

Примеры палиндромов и непалиндромов

Примеры палиндромных и непалиндромных строк

Пары примеров:

“madam” — палиндром
“racecar” — палиндром
“mom” — палиндром
“MUO” — не палиндром (если сравнивать без нормализации регистра)
“MAKEUSEOF” — не палиндром

Алгоритм проверки палиндрома (двухуказательный)

Краткий план (двухуказательный метод):

Привести строку к единому регистру (например, к нижнему).
Установить два указателя: low = 0 и high = n-1, где n — длина строки.
Пока low < high:
- Если str[low] != str[high], строка не палиндром — вернуть false.
- Иначе увеличить low и уменьшить high.
Если цикл закончился без несоответствия, строка — палиндром.

Пояснение: метод сравнивает пары символов с концов к центру. Время O(n), память O(1).

Важная опция: если надо игнорировать пробелы и знаки препинания, предварительно отфильтруйте символы, оставив только буквы и цифры.

Альтернативные подходы

Реверс строки: сравнить исходную строку (в нижнем регистре) с её перевёрнутой копией. Проще, но требует O(n) дополнительной памяти.
Рекурсивный подход: рекурсивно сравнивать первый и последний символы. Подходит для учебных примеров, но использует стек вызовов.
Использовать регулярные выражения для очистки строки (удалить все не-алфанумерические символы) и затем применить один из методов выше.

Когда алгоритм двухуказательного метода не подходит

Когда нужно учитывать нормализацию Unicode (некоторые символы имеют составные формы). Тогда требуется нормализация Unicode (NFC/NFD).
Если нужно игнорировать знаки препинания и пробелы — предварительно фильтруйте строку.

Базовая схема принятия решения (мертвые простые правила)

Если симметричны все пары символов — палиндром.
Если найдена первая несоответствующая пара — не палиндром.

C++: проверка палиндрома

// Включение библиотек
#include 
using namespace std;

// Функция для проверки палиндрома
void checkPalindrome(string str)
{
    // Флаг: предполагаем, что строка — палиндром
    bool flag = true;

    // Длина строки
    int n = str.length();

    // Перевод в нижний регистр
    for (int i = 0; i < n; i++)
    {
        str[i] = tolower((unsigned char)str[i]);
    }

    int low = 0;
    int high = n - 1;

    while (high > low)
    {
        if (str[high] != str[low])
        {
            flag = false;
            break;
        }
        low++;
        high--;
    }

    if (flag)
    {
        cout << "Да, строка является палиндромом" << endl;
    }
    else
    {
        cout << "Нет, строка не является палиндромом" << endl;
    }
}

int main()
{
    string str1 = "MUO";
    checkPalindrome(str1);

    string str2 = "madam";
    checkPalindrome(str2);

    string str3 = "MAKEUSEOF";
    checkPalindrome(str3);

    string str4 = "racecar";
    checkPalindrome(str4);

    string str5 = "mom";
    checkPalindrome(str5);

    return 0;
}

Вывод (пример):

Нет, строка не является палиндромом
Да, строка является палиндромом
Нет, строка не является палиндромом
Да, строка является палиндромом
Да, строка является палиндромом

Python: проверка палиндрома

# Функция для проверки палиндрома
def checkPalindrome(s):
    # Флаг: предполагаем, что строка — палиндром
    flag = True

    # Длина строки
    n = len(s)

    # Перевод в нижний регистр
    s = s.lower()

    low = 0
    high = n - 1

    while high > low:
        if s[high] != s[low]:
            flag = False
            break
        low += 1
        high -= 1

    if flag:
        print("Да, строка является палиндромом")
    else:
        print("Нет, строка не является палиндромом")

# Тесты
checkPalindrome("MUO")
checkPalindrome("madam")
checkPalindrome("MAKEUSEOF")
checkPalindrome("racecar")
checkPalindrome("mom")

Вывод:

Нет, строка не является палиндромом
Да, строка является палиндромом
Нет, строка не является палиндромом
Да, строка является палиндромом
Да, строка является палиндромом

C: проверка палиндрома

// Включение библиотек
#include 
#include 
#include 
#include 

// Функция для проверки палиндрома
void checkPalindrome(char str[])
{
    bool flag = true;
    int n = strlen(str);

    for (int i = 0; i < n; i++)
    {
        str[i] = tolower((unsigned char)str[i]);
    }

    int low = 0;
    int high = n - 1;

    while (high > low)
    {
        if (str[high] != str[low])
        {
            flag = false;
            break;
        }
        low++;
        high--;
    }

    if (flag)
    {
        printf("Да, строка является палиндромом\n");
    }
    else
    {
        printf("Нет, строка не является палиндромом\n");
    }
}

int main()
{
    char str1[] = "MUO";
    checkPalindrome(str1);

    char str2[] = "madam";
    checkPalindrome(str2);

    char str3[] = "MAKEUSEOF";
    checkPalindrome(str3);

    char str4[] = "racecar";
    checkPalindrome(str4);

    char str5[] = "mom";
    checkPalindrome(str5);

    return 0;
}

Вывод:

Нет, строка не является палиндромом
Да, строка является палиндромом
Нет, строка не является палиндромом
Да, строка является палиндромом
Да, строка является палиндромом

JavaScript: проверка палиндрома

// Функция для проверки палиндрома
function checkPalindrome(str) {
    var flag = true;
    var n = str.length;

    str = str.toLowerCase();

    var low = 0;
    var high = n - 1;

    while (high > low) {
        if (str[high] != str[low]) {
            flag = false;
            break;
        }
        low++;
        high--;
    }

    if (flag) {
        console.log("Да, строка является палиндромом");
    } else {
        console.log("Нет, строка не является палиндромом");
    }
}

checkPalindrome("MUO");
checkPalindrome("madam");
checkPalindrome("MAKEUSEOF");
checkPalindrome("racecar");
checkPalindrome("mom");

Вывод в консоли:

Нет, строка не является палиндромом
Да, строка является палиндромом
Нет, строка не является палиндромом
Да, строка является палиндромом
Да, строка является палиндромом

Как учесть пробелы и пунктуацию

Если надо игнорировать пробелы и знаки препинания, предварительно оставьте только буквы и цифры. Пример на Python:

import re
s = "A man, a plan, a canal: Panama"
filtered = re.sub(r'[^0-9a-zA-Z]', '', s).lower()
# затем можно сравнить filtered == filtered[::-1]

Сложность алгоритма — сводка

Факт-бокс:

Время (двухуказательный метод): O(n)
Память: O(1) дополнительной памяти
Время (метод с реверсом): O(n)
Память (реверс): O(n)

Ментальные модели и эвристики

Подумайте о зеркале: сравниваем соответствующие символы от краёв к центру.
Для больших строк выбирайте двухуказательный метод, чтобы минимизировать память.
Если входные данные содержат Unicode, нормализуйте строку перед сравнением.

Критерии приёмки

Функция возвращает true/false (или эквивалент) корректно для всех тестов.
Обрабатываются разные регистры (A и a считаются одинаковыми).
Для опции «игнорировать небуквенно-цифровые символы» все такие символы удаляются перед сравнением.
Для больших строк алгоритм масштабируем и не использует лишней памяти.

Тест-кейсы и примеры для приёма

Вход: “”, ожидаемый результат: палиндром (пустая строка).
“a” → палиндром.
“ab” → не палиндром.
“aba” → палиндром.
“A man, a plan, a canal: Panama” (с фильтрацией) → палиндром.

Рольные чек-листы

Для разработчика:

Реализовать двухуказательный алгоритм.
Добавить опцию фильтрации небуквенно-цифровых символов.
Нормализовать регистр/Unicode.

Для ревьюера:

Проверить граничные случаи (пустая строка, один символ).
Проверить поведение при не-ASCII символах.

Для тестировщика:

Автоматизировать тесты с набором строк разной длины и состава.

Диаграмма принятия решения

flowchart TD
    A[Начало] --> B{Фильтровать небуквенно-цифровые?}
    B -- Да --> C[Удалить все кроме букв/цифр]
    B -- Нет --> C
    C --> D[Привести к одному регистру]
    D --> E[Установить low и high]
    E --> F{low < high}
    F -- Да --> G{str[low] == str[high]}
    G -- Да --> H[low++, high--] --> F
    G -- Нет --> I[Не палиндром]
    F -- Нет --> J[Палиндром]

Небольшая шпаргалка (cheat sheet)

Метод: двухуказательный — худшее/среднее время O(n), память O(1).
Быстрая проверка (облегчённая): s.lower() == s.lower()[::-1] (Python) — удобно, но требует память.

1-строчный глоссарий

Палиндром: строка, равная своей обратной.
Двухуказательный (two-pointer): алгоритмическая техника с двумя индексами, начинающимися с краёв.

Заключение

Двухуказательный алгоритм — надёжный и эффективный способ проверить, является ли строка палиндромом. Для большинства практических задач он обеспечивает оптимальное сочетание времени и памяти. Если вход содержит пробелы или знаки препинания, дополнительно фильтруйте строку.

Короткое объявление для соцсетей: “Узнайте, как проверить, является ли строка палиндромом — простые алгоритмы и готовые реализации на C++, Python, C и JavaScript.”