MiddleКодЧастоЕщё не отвечали
Проверка палиндрома без учёта пунктуации за O(n)
Дана строка из букв и знаков препинания. Верните True, если она читается одинаково в обе стороны, игнорируя не-буквенные символы и регистр.
Требования:
- O(n) время, O(1) доп. память (два указателя).
- Пропускайте пунктуацию, а не вырезайте её в новую строку.
def is_palindrome(s):
# ваш код здесьДопишите реализацию.
Используйте два указателя: left в начале и right в конце. Двигайте каждый мимо не-букв, затем сравните s[left].lower() с s[right].lower(); при несовпадении верните False, иначе сдвиньте оба внутрь. Остановитесь, когда они пересекутся. Это O(n) время и O(1) память — без новой отфильтрованной строки. Инициализация right как len(s)-1 (а не -1) спасает от ошибки на единицу.
- ✗Выделять новую отфильтрованную строку, получая O(n) память вместо O(1)
- ✗Забывать привести символы к нижнему регистру перед сравнением
- ✗Ошибка на единицу от инициализации правого указателя как
-1вместоlen(s)-1
- →Как два указателя пропускают пунктуацию без построения новой строки?
- →Какие крайние случаи (пустая строка, только пунктуация) должен обработать цикл?
Оглавление
Задача
Реализуйте is_palindrome: проверьте палиндромность строки, игнорируя пунктуацию и регистр, за O(n) и O(1) память.
Решение
def is_palindrome(s):
left, right = 0, len(s) - 1
while left < right:
if not s[left].isalpha():
left += 1
elif not s[right].isalpha():
right -= 1
elif s[left].lower() != s[right].lower():
return False
else:
left += 1
right -= 1
return TrueКлючевые моменты
- Два указателя пропускают не-буквы на месте — без новой строки, поэтому память O(1).
- Сравниваем в нижнем регистре, чтобы игнорировать регистр.
right = len(s) - 1(не-1) — иначе ошибка на единицу при выходе из цикла.
Оглавление
