125. Valid Palindrome

Easy

Problem:

Determine if the provided string is a palindrome. This should be case-insensitive and should only take into account English letters and numbers.

For example, "A man, a plan, a canal: Panama" is a palindrome. "race a car" is not a palindrome.

Note: Since an empty string reads the same forward and backward, it is a palindrome.

Input: "A man, a plan, a canal: Panama"
Output: true

https://leetcode.com/problems/valid-palindrome/

What to learn:

• string.isalnum(): returns True if all the characters are alphanumeric, meaning alphabet letter (a-z) and numbers (0-9). Example of characters that are not alphanumeric: (space)!#%&? etc.

• list.pop(index): removes the item at the given index from the list and returns the removed item. pop() returns the last value from the list.

Solutions:

1. Preprocess the provided string.

2. Compare the first character of string and the last one.

List

class Solution:
    def isPalindrome(self, s: str) -> bool:
        ch = list(s.lower())
        l = []
        for i in range(len(ch)):
            if ch[i].isalnum():
                l.append(ch[i])

        for i in range(len(l)):
            if l[i] == l[len(l) - i - 1]:
                continue
            else:
                return False
        return True

Stack solution

class Solution:
    def isPalindrome(self, s: str) -> bool:
        strs = []
        for char in s:
            if char.isalnum():
                strs.append(char.lower())
        while len(strs) > 1:
            if strs.pop(0) != strs.pop():
                return False
        return True

Deque

While popping the first element from a list has a time complexity of $O(n)$, doing the same operation with a deque, using popleft(), has a time complexity of $O(1)$. Therefore, if you repeat either operation n times, the list operation would have a time complexity of $O(n^2)$, whereas the deque operation would remain at $O(n)$. This results in a substantial performance difference between the two.

class Solution:
    def isPalindrome(self, s: str) -> bool:
        strs: Deque = collections.deque()
        for char in s:
            if char.isalnum():
                strs.append(char.lower())
        while len(strs) > 1:
            if strs.popleft() != strs.pop():
                return False
        return True

Slicing

1. Filtering the string leaving only alphanumeric characters with a regular expression

2. Flipping the string backwards using the [::-1] slicing operation

import re
class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = s.lower()
        s = re.sub('[^a-z0-9]','', s)
        return s == s[::-1]