Valid Palindrome

Лёгкая№125навстречу

Дана строка. Нужно понять, читается ли она одинаково слева направо и справа налево, если оставить только буквы и цифры и не различать большие и маленькие буквы. Наш пример: «Taco, cat!» — да, это палиндром.

125 Valid PalindromeРазбор · 1×

Пример: «Taco, cat!». Указатели идут с двух концов навстречу и пропускают всё, что не буква и не цифра.

0T1a2c3o4,5␣6c7a8t9!left
ещё не провереныпод указателемсовпалипропущены

left — на первом символе, «T»

01/34
сначала · назад · пуск · шаг
Скорость
1function isPalindrome(s):
2 left = 0
3 right = len(s) - 1
4 while left < right:
5 if not isLetterOrDigit(s[left]):
6 left = left + 1
7 else if not isLetterOrDigit(s[right]):
8 right = right - 1
9 else if lower(s[left]) != lower(s[right]):
10 return false
11 else:
12 left = left + 1; right = right - 1
13 return true
состояние
left
0
right
–
s[left]
T
s[right]
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Палиндром — это когда первый символ равен последнему, второй — предпоследнему и так далее. Значит, сравниваем с двух концов.
  2. Знаки и пробелы в сравнении не участвуют: указатель просто перешагивает их.
  3. Первая же несовпавшая пара — ответ «нет». Указатели встретились — ответ «да».

Сложность

Время O(n): каждый указатель проходит строку не больше одного раза. Память O(1): копию строки не делаем.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.