Valid Palindrome

Instructions

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

Approach

We will remove any spaces and non-alphanumeric characters in the given string, convert the letters to lowercase and then compare if the new string is equal to its reversed equivalent.

Python Implementation

In this solution, we filter the string to remove non-alphanumeric characters, we convert the iterator to a list and use the join method to convert the list to a string. Then we convert the string to lowercase and compare if it is equal to the reversed string.

The filter() method filters the given iterable and returns an iterator that is already filtered that satisfies the conditions specified by the function passed as a parameter.

def isPalindrome(self, s: str) -> bool:
        a = "".join(list(filter(str.isalnum, s))).lower()
        return a == a[::-1]

We can also achieve the same results using the code below:

def isPalindrome(self, s: str) -> bool:
        newStr = ""
        s = s.lower()

        for i in s:
            if i.isalnum():
                newStr += i
        return True if newStr == newStr[::-1] else False 

The time complexity if O(n) because we iterate through the string once.
The space complexity is O(n) because we need extra memory for the new string we create.

Two-Pointer Approach

We can also initialize pointers at the beginning and at the end of the string and compare each letter. If the letters differ we return false

Python Implementation

def isPalindrome(self, s: str) -> bool:

        newStr = ''
        for i in s:
            if i.isalnum():
                newStr += i
        newStr = newStr.lower()
        start = 0
        end = len(newStr)-1
        while start < end:
            if newStr[start] == newStr[end]:
                start += 1
                end += -1
            else:
                return False
        return True