Interview challenge · easy · string, two-pointers
Valid Palindrome
El reto
El enunciado va en inglés, igual que en el vídeo.
A phrase is a palindrome if, after converting uppercase letters to lowercase and removing all non-alphanumeric characters, it reads the same forward and backward. Given a string s, return whether it is a palindrome.
Example
"A man, a plan, a canal: Panama" -> true
"race a car" -> falseIdea: two pointers, one at each end. Skip anything that is not a letter or digit, compare the lowercase characters, and move inward. Time O(n), space O(1).
La solución
# Valid Palindrome - ayotl.dev
def is_palindrome(s):
# two pointers walking inward
i, j = 0, len(s) - 1
while i < j:
if not s[i].isalnum():
i += 1 # skip punctuation
elif not s[j].isalnum():
j -= 1
elif s[i].lower() != s[j].lower():
return False # mismatch
else:
i, j = i + 1, j - 1
return True
print(is_palindrome(
"A man, a plan, a canal: Panama"))
print(is_palindrome("race a car"))
$ python3 valid_palindrome.py
True
False