Сегодня мы обсудим однопроходное решение задачи о допустимом палиндроме.
Палиндром — это строка, которая при чтении от 0-n или n-0 остается одинаковой. означает, что если вы прочитаете его вперед или назад, оно будет одинаковым.
например, «талат»
Итак, мы можем проверить это за один проход, если сможем одновременно перебирать строку вперед и назад. и проверьте, все ли символы одинаковы или нет. Идея, лежащая в основе этого, может быть реализована методом «двух указателей». один указатель движется вперед по строке, а другой - назад.
В Python это можно сделать следующим образом:
class Solution:
def isPalindrome(self, s: str) -> bool:
cleaned_str = re.sub(r'[^a-zA-Z0-9]' , '' , s.lower())
# special case when there is an empty string.
# empty string is a palindrome too.
if cleaned_str == "":
return True
# we check for each forward and backward.
# if there is no match, we break and return False
# otherwise after the loop, we return True
# because, after loop string must have passed palindrome condition.
for i in range(len(cleaned_str)):
if cleaned_str[i] != cleaned_str[-(i+1)]:
return False
return True
В приведенном выше коде cleaned_str[i]является указателем вперед и в тот же момент времени cleaned_str[-(i +1)] — это указатель назад.
Потому что, если мы находимся в нулевом индексе, то clean_str[-(i+1)] будет равен -1, что является последним индексом. Следовательно, мы перебираем строку следующим образом.
