Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
Have you consider that the string might be empty? This is a good question to ask during an interview.
For the purpose of this problem, we define empty string as valid palindrome.
Example 1:
Input: "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama"
Example 2:
Input: "race a car"
Output: false
Explanation: "raceacar"
Challenge
O(n) time without extra memory.
up > low
class Solution:
"""
@param s: A string
@return: Whether the string is a valid palindrome
"""
def isPalindrome(self, s):
# corner case
if len(s) <= 1:
return True
# init 2 pointers
low = 0
up = len(s) - 1
# while not meet
while up > low:
# case 1 low is not letter
if not (s[low].isalpha() or s[low].isdigit()):
low += 1
continue
# case 2 up is not letter
if not (s[up].isalpha() or s[up].isdigit()):
up -= 1
continue
# case 3 same letter
if s[up].lower() == s[low].lower():
up -= 1
low += 1
else: # if difference found
return False
# return true if no difference found
return True