JuniorКодОчень частоЕщё не отвечали
Напишите функцию для определения, является ли слово палиндромом
Дана строка. Верните true, если она читается одинаково в обе стороны.
Требования:
- O(n) время, O(1) доп. память (два указателя — не разворачивайте в буфер).
- Пустая строка и строка из одного символа являются палиндромами.
#include <string>
bool isPalindrome(const std::string& s) {
// ваш код здесь
}Допишите реализацию.
Используйте два указателя с обоих концов, движущихся к центру. Сравниваем символы; если они различаются — строка не является палиндромом. Время O(n), память O(1).
- ✗Разворачивать всю строку и сравнивать — излишне выделяет O(n) дополнительной памяти
- ✗Не учитывать регистр или неалфавитно-цифровые символы для реальных входных данных
- ✗Использовать знаковую арифметику индексов, которая может уйти в отрицательные значения при пустой строке
- →Как проверить, является ли связный список палиндромом?
- →Что такое задача нахождения наидлиннейшей палиндромной подстроки и какой алгоритм эффективно её решает?
Оглавление
Задача
Напишите функцию, которая проверяет, является ли строка палиндромом (читается одинаково в обоих направлениях).
Решение
#include <string>
#include <cctype>
#include <cassert>
// Базовое решение — точное совпадение символов
bool isPalindrome(const std::string& s) {
int left = 0;
int right = static_cast<int>(s.size()) - 1;
while (left < right) {
if (s[left] != s[right]) return false;
++left;
--right;
}
return true;
}
// Расширенное — игнорирует регистр и не-алфавитно-цифровые символы
bool isPalindromeRelaxed(const std::string& s) {
int left = 0;
int right = static_cast<int>(s.size()) - 1;
while (left < right) {
while (left < right && !std::isalnum(s[left])) ++left;
while (left < right && !std::isalnum(s[right])) --right;
if (std::tolower(s[left]) != std::tolower(s[right])) return false;
++left;
--right;
}
return true;
}
int main() {
assert( isPalindrome("racecar"));
assert( isPalindrome(""));
assert( isPalindrome("a"));
assert(!isPalindrome("hello"));
assert( isPalindromeRelaxed("A man, a plan, a canal: Panama"));
assert(!isPalindromeRelaxed("race a car"));
}Ключевые моменты
- Два указателя: O(n) время, O(1) память — оптимально.
- Разворот строки с последующим сравнением — правильно, но тратит O(n) памяти.
- Для задач с реальными данными нормализуйте: нижний регистр + пропуск непечатаемых символов.
Оглавление
