Проверка строки на палиндром — алгоритм и примеры

Иллюстрация перемешанных символов

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

Палиндром — это строка, которая остаётся одинаковой при прочтении справа налево и слева направо. Примеры: “madam”, “racecar”, “mom”. Важно: понятие палиндрома зависит от правил сравнения (учитываются ли регистр, пробелы, знаки препинания, Unicode-нормализация и т. д.).

Быстрая идея алгоритма

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

Преимущества: O(n) по времени и O(1) по дополнительной памяти (если не делать копий строки). Альтернатива — обратить строку и сравнить с исходной (удобно, но потребляет O(n) памяти).

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

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

Пошаговый алгоритм проверки палиндрома

Объявите функцию, принимающую строку как параметр.
Заведите булеву переменную flag и установите true.
Найдите длину строки n.
Приведите строку к нижнему регистру для нечувствительного к регистру сравнения (по необходимости).
Инициализируйте low = 0.
Инициализируйте high = n - 1.
Пока low < high:
- Сравните символы str[low] и str[high].
- Если не совпадают, установите flag = false и прервите цикл.
- Иначе увеличьте low и уменьшите high.
Если flag == true — строка палиндром.
Иначе — не палиндром.

Совет: часто полезно сначала удалить из строки пробелы и знаки пунктуации и нормализовать Unicode, если вы хотите учитывать только буквы и цифры.

Сложности и эффективность

Временная сложность: O(n), где n — длина строки.
Дополнительная память: O(1) для двухуказательного метода; O(n) для метода с созданием перевёрнутой копии.

Когда метод может дать неожиданный результат (ограничения)

Unicode: комбинирующие знаки и разные формы символов (NFC vs NFD) могут потребовать нормализации.
Локаль: правила приведения к нижнему регистру различаются для некоторых языков (например, турецкая i).
Пробелы и пунктуация: решить заранее — считать их или игнорировать.
Диакритика: é vs e — требуется приведение к базовой форме, если нужно.

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

C++ Программа для проверки палиндрома

Ниже — реализация метода двух указателей (комментарии оставлены в оригинальном виде):

// Including libraries  
#include   
using namespace std;  
  
// Function to check string palindrome  
void checkPalindrome(string str)  
{  
 // Flag to check if the given string is a palindrome  
 bool flag = true;  
  
 // Finding the length of the string  
 int n = str.length();  
  
 // Converting the string to lowercase  
 for(int i = 0; i < n; i++)  
 {   
 str[i] = tolower(str[i]);   
 }   
  
 // Initializing low index variable  
 int low = 0;  
  
 // Initializing high index variable  
 int high = n-1;  
  
 // Running the loop until high is greater than low  
 while (high > low)  
 {  
 // If the characters are not same, set the flag to false   
 // and break from the loop  
 if(str[high] != str[low])  
 {   
 flag = false;   
 break;   
 }   
  
 // Increment the low index variable  
 low++;  
  
 // Decrement the high index variable  
 high--;  
 }  
  
 // Check if flag is true or false  
 if (flag)  
 {  
 cout << "Yes, the given string is a palindrome" << endl;  
 }  
 else  
 {  
 cout << "No, the given string is not a palindrome" << endl;  
 }  
  
 return;  
  
}  
  
int main()  
{  
 // Test case: 1  
 string str1 = "MUO";  
 checkPalindrome(str1);  
  
 // Test case: 2  
 string str2 = "madam";  
 checkPalindrome(str2);  
  
 // Test case: 3  
 string str3 = "MAKEUSEOF";  
 checkPalindrome(str3);  
  
 // Test case: 4  
 string str4 = "racecar";  
 checkPalindrome(str4);  
  
 // Test case: 5  
 string str5 = "mom";  
 checkPalindrome(str5);  
  
 return 0;  
}

Вывод программы:

No, the given string is not a palindrome   
Yes, the given string is a palindrome   
No, the given string is not a palindrome   
Yes, the given string is a palindrome   
Yes, the given string is a palindrome

Python Программа для проверки палиндрома

Реализация двухуказательного метода в Python (комментарии в исходном виде):

# Function to check string palindrome  
def checkPalindrome(str):  
  
    # Flag to check if the given string is a palindrome  
    flag = True  
  
    # Finding the length of the string  
    n = len(str)  
  
    # Converting the string to lowercase  
    str = str.lower()  
  
    # Initializing low index variable  
    low = 0  
  
    # Initializing high index variable  
    high = n-1  
  
    # Running the loop until high is greater than low  
    while high > low:  
        # If the characters are not same, set the flag to false  
        # and break from the loop  
        if str[high] != str[low]:  
            flag = False  
            break  
  
        # Increment the low index variable  
        low = low + 1  
  
        # Decrement the high index variable  
        high = high - 1  
  
    # Check if flag is true or false  
    if flag:  
        print("Yes, the given string is a palindrome")  
    else:  
        print("No, the given string is not a palindrome")  
  
# Test case: 1  
str1 = "MUO"  
checkPalindrome(str1)  
  
# Test case: 2  
str2 = "madam"  
checkPalindrome(str2)  
  
# Test case: 3  
str3 = "MAKEUSEOF"  
checkPalindrome(str3)  
  
# Test case: 4  
str4 = "racecar"  
checkPalindrome(str4)  
  
# Test case: 5  
str5 = "mom"  
checkPalindrome(str5)

Вывод:

No, the given string is not a palindrome  
Yes, the given string is a palindrome  
No, the given string is not a palindrome  
Yes, the given string is a palindrome  
Yes, the given string is a palindrome

C Программа для проверки палиндрома

Реализация на C (сохранены исходные комментарии):

// Including libraries  
#include   
#include   
#include   
#include   
  
// Function to check string palindrome  
void checkPalindrome(char str[])  
{  
 // Flag to check if the given string is a palindrome  
 bool flag = true;  
  
 // Finding the length of the string  
 int n = strlen(str);  
  
 // Converting the string to lowercase  
 for(int i = 0; i < n; i++)  
 {  
 str[i] = tolower(str[i]);  
 }  
  
 // Initializing low index variable  
 int low = 0;  
  
 // Initializing high index variable  
 int high = n-1;  
  
 // Running the loop until high is greater than low  
 while (high > low)  
 {  
 // If the characters are not same, set the flag to false  
 // and break from the loop  
 if(str[high] != str[low])  
 {  
 flag = false;  
 break;  
 }  
  
 // Increment the low index variable  
 low++;  
  
 // Decrement the high index variable  
 high--;  
 }  
  
 // Check if flag is true or false  
 if (flag)  
 {  
 printf("Yes, the given string is a palindrome \\n");  
 }  
 else  
 {  
 printf("No, the given string is not a palindrome \\n");  
 }  
  
 return;  
  
}  
  
int main()  
{  
 // Test case: 1  
 char str1[] = "MUO";  
 checkPalindrome(str1);  
  
 // Test case: 2  
 char str2[] = "madam";  
 checkPalindrome(str2);  
  
 // Test case: 3  
 char str3[] = "MAKEUSEOF";  
 checkPalindrome(str3);  
  
 // Test case: 4  
 char str4[] = "racecar";  
 checkPalindrome(str4);  
  
 // Test case: 5  
 char str5[] = "mom";  
 checkPalindrome(str5);  
  
 return 0;  
}

Вывод:

No, the given string is not a palindrome   
Yes, the given string is a palindrome   
No, the given string is not a palindrome   
Yes, the given string is a palindrome   
Yes, the given string is a palindrome

JavaScript Программа для проверки палиндрома

Реализация на JavaScript:

// Function to check string palindrome  
function checkPalindrome(str) {  
    // Flag to check if the given string is a palindrome  
    var flag = true;  
  
    // Finding the length of the string  
    var n = str.length;  
  
    // Converting the string to lowercase  
    str = str.toLowerCase();  
  
    // Initializing low index variable  
    var low = 0;  
  
    // Initializing high index variable  
    var high = n-1;  
  
    // Running the loop until high is greater than low  
    while (high > low) {  
        // If the characters are not same, set the flag to false  
        // and break from the loop  
        if(str[high] != str[low]) {  
            flag = false;  
            break;  
        }  
  
        // Increment the low index variable  
        low++;  
  
        // Decrement the high index variable  
        high--;  
    }  
  
    // Check if flag is true or false  
    if (flag) {  
        console.log("Yes, the given string is a palindrome");  
    } else {  
        console.log("No, the given string is not a palindrome");  
    }  
  
}  
  
// Test case: 1  
var str1 = "MUO";  
checkPalindrome(str1);  
  
// Test case: 2  
var str2 = "madam";  
checkPalindrome(str2);  
  
// Test case: 3  
var str3 = "MAKEUSEOF";  
checkPalindrome(str3);  
  
// Test case: 4  
var str4 = "racecar";  
checkPalindrome(str4);  
  
// Test case: 5  
var str5 = "mom";  
checkPalindrome(str5);

Вывод:

No, the given string is not a palindrome  
Yes, the given string is a palindrome  
No, the given string is not a palindrome  
Yes, the given string is a palindrome  
Yes, the given string is a palindrome

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

Сравнение с перевёрнутой строкой: удобно и коротко (например, в Python str == str[::-1]), но требует O(n) дополнительной памяти.
Использование стека: положить половину символов в стек, затем сравнить — полезно при потоковой обработке.
Рекурсивная проверка: наглядна, но использует стек вызовов и неэффективна по памяти.
Игнорирование небуквенных символов: предварительно фильтруйте строку (regex или явный проход).

Ментальная модель: думайте о двух указателях как о проверке зеркального отражения строки.

Факто-бокс

Время: O(n)
Память: O(1) (двухуказательный метод) или O(n) (создание перевёрнутой строки)
Подходит для: ASCII и простых задач без нормализации
Требует внимания: Unicode, локаль и нормализация

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

Функция корректно определяет палиндромы для латинских букв без пробелов и пунктуации.
При опции «игнорировать небуквенные символы» результаты совпадают с ожидаемыми для строк с пробелами и знаками.
Производительность: для строк длиной до 10^6 функция выполняется за линейное время и не использует значительную дополнительную память.

Тестовые случаи

Пустая строка -> считать палиндромом (по соглашению).
Однобуквенная строка -> палиндром.
“A man, a plan, a canal: Panama” при игнорировании пробелов и пунктуации -> палиндром.
Строки с разным регистром: “Madam” -> палиндром при нечувствительном к регистру сравнении.
Unicode-строки с комбинирующими знаками -> требует нормализации.

Быстрый чек-лист для разработчика

Решить правила сравнения (регистр, пробелы, пуктуация, Unicode).
Реализовать метод двух указателей для O(1) памяти.
Добавить тесты для граничных случаев.
Документировать локаль и нормализацию.

Короткое резюме

Двухуказательный алгоритм — простой и эффективный способ проверить, является ли строка палиндромом. Перед применением в проде согласуйте правила нормализации и локаль, особенно при работе с Unicode.

Как разбираться со строками в программировании

Работа со строками — ключевой навык. Знание операций: приведение регистра, фильтрация символов, нормализация Unicode, сравнение и реверсирование строки — жизненно важно. Для начинающих Python часто наиболее удобен из-за лаконичности и мощных встроенных средств для работы со строками.