MiddleКодИногдаЕщё не отвечали
Можно ли сделать строку палиндромом, удалив ровно один символ?
Дана непустая строка. Определите, можно ли удалением ровно одного символа сделать её палиндромом. Если строка уже палиндром, ответ true (удалить центральный символ). "aaab" → true, "xyz" → false.
Требования:
- O(n) по времени, O(1) доп. памяти.
bool canBePalindromeAfterOneRemoval(const std::string& s) {
// ваш код здесь
}Допишите реализацию.
Два указателя с обоих концов. На первом несовпадении попробуйте пропустить левый или правый символ и проверьте, палиндром ли оставшийся участок. Если строка уже палиндром, удаление центрального символа сохранит его, так что верните true. O(n), O(1).
- ✗Трактовать спецификацию как «не более одного» удаления, тогда как сказано «ровно одно»
- ✗Проверять лишь одну сторону на несовпадении вместо обоих удалений
- ✗Перепросматривать всю строку для каждого кандидата на удаление, делая O(n²)
- →Чем «ровно одно» тонко отличается от «не более одного» для уже-палиндромной строки?
- →Почему достаточно попробовать обе стороны на первом несовпадении?
Оглавление
Задача
Определите, можно ли удалением ровно одного символа сделать строку палиндромом, за O(n).
Решение
#include <string>
static bool isPal(const std::string& s, int i, int j) {
while (i < j) { if (s[i++] != s[j--]) return false; }
return true;
}
bool canBePalindromeAfterOneRemoval(const std::string& s) {
int i = 0, j = s.size() - 1;
while (i < j) {
if (s[i] != s[j])
return isPal(s, i + 1, j) || isPal(s, i, j - 1);
++i; --j;
}
return true; // уже палиндром -> удаляем центральный
}Ключевые моменты
- Сходимся указателями до первого несовпадения.
- Там пробуем пропустить левый ИЛИ правый символ.
- Уже-палиндром тоже даёт true (удаляем центральный символ).
Оглавление
