🔁125. Valid Palindrome

Easy | Grind 75 | August 17 Wednesday, 2022

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.

Constraints:

• 1 <= s.length <= 2 * 105

• s consists only of printable ASCII characters.

Example 1

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Second Tab

Input: s = "race a car"
Output:false
Explanation:"raceacar" is not a palindrome.

Example 3

Input: s = " "
Output:true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.

SOLUTION

There are different ways to solve this problem. We first need to clean the string to contain only alphanumeric characters. Then, one solution is to reverse the string and compare if the characters are the same at each index. Another solution is to have two pointers, one at the start of the string and one at the end. We comapre the characters at the start and end of the string. If the characters match, the start pointer is incremented by 1 and the end pointer is decremented by 1. If the characters do not match, the string is not a palindrome. We repeat this until the start and end pointer points to the same character.

class Solution:
    def isPalindrome(self, s: str) -> bool:
        # create a new string consisting only of lowercase alphanumeric character
        new_s = ""
        for char in s: 
            if char.isalnum():
                new_s+= char.lower()
        
        
        # two pointers to compare the characters on two opposing sides.
        start, end = 0, len(new_s)-1
        
        # compare the start and the end character of the string
        while start < end: 
            # if the two characters dont match, not a palindrome
            if new_s[start] != new_s[end]:
                return False
            
            start += 1
            end -= 1
                
        return True

TIME AND SPACE COMPLEXITY

TIME: O(n) where n is the length of the string. We have to iterate over every character once to create the new string. And then iterate another n times(worst case) to check for character mismatch.

SPACE: O(n) given that we are create a new string, in the worst case we will need n space to copy every character from the original string.

*written with help from OpenAI GPT-3 model