Проверка палиндрома с пропуском лишних символов: где ломается инвариант цикла
Функция проверяет, что строка — палиндром, если учитывать только буквы и цифры и игнорировать регистр:
def is_palindrome(s):
left, right = 0, len(s) - 1
while left < right:
if not s[left].isalnum():
left += 1
if not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return True
На строке "A man, a plan, a canal: Panama" функция возвращает False, хотя должна вернуть True. В чём дефект?
- Пропуск неалфавитных символов сделан через `if` вместо `while`: подряд идущие разделители снимаются не полностью, и сравнение выполняется, когда указатель всё ещё стоит на разделителе
- Условие цикла должно быть `left <= right`: при нечётной длине центральный символ не проверяется
- `isalnum` возвращает True для пробела, поэтому пробелы и знаки препинания не отфильтровываются
- Нужно вызывать `s.lower()` один раз до цикла: посимвольный `lower()` внутри цикла даёт неверный результат для латиницы
- Указатели нельзя двигать безусловно в конце тела цикла: `left += 1` и `right -= 1` после сравнения пропускают по одному символу за итерацию, из-за чего половина букв не проверяется