- Published on
Valid Palindrome
- Authors
- Name
- Alex Noh
Introduction
Palindrome is a string(a list of character) that maintains its original spelling when read both forwards and backwards. "radar", "level" and "kayak" can be some of the examples.
It can also be a sentence like "Madam, in Eden I'm Adam."
Problem
Check if a string is a palindrome or not. Palindromes are case-insensitive, consist of alpha-numeric characters.
Things you should know
A built-in function to tell if a character is a number or an alphabet
main.py
# isalnum()
print('s'.isalnum()) # True
print('.'.isalnum()) # False
Solutions
1. Naïve one (without any thinking)
main.py
import re
def preprocess(text: str) -> str:
return re.sub(r'[^a-zA-Z0-9]', '', text).lower()
def is_palindrome(text: str) -> bool:
refined_text = list(preprocess(text))
while len(refined_text) > 1:
if refined_text.pop(0) != refined_text.pop():
return False
return True
2. Using deque
You can use deque(stands for double-ended queue).
By using deque, you can reduce the execution time down to 1/5 of the first solution. see here for more information
main.py
import re
from collections import deque
def preprocess(text: str) -> str:
return re.sub(r'[^a-zA-Z0-9]', '', text).lower()
def is_palindrome(text: str) -> bool:
refined_text = deque(preprocess(text))
while len(refined_text) > 1:
if refined_text.popleft() != refined_text.pop():
return False
return True
3. Using the 'slicing'
You can use the built-in slice of list. By setting the step to -1, you can reverse the string.
main.py
import re
def preprocess(text: str) -> str:
return re.sub(r'[^a-zA-Z0-9]', '', text).lower()
def is_palindrome(text: str) -> bool:
s = preprocess(text.lower())
return str == str[::-1]