Valid Palindrome LeetCode 125

20 Jan 2024

Reading time ~1 minute

Intuition

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.

Example 1:

Input: s = “A man, a plan, a canal: Panama” Output: true Explanation: “amanaplanacanalpanama” is a palindrome. Example 2:

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.

Constraints:

1 <= s.length <= 2 * 105 s consists only of printable ASCII characters.

Approach

Using functions (filtering w/ isalum(), converting lower() and check reverse)
Two pointers

ref: https://www.youtube.com/watch?v=jJXJ16kPFWg&ab_channel=NeetCode

Complexity

Time complexity: O(N)
Space complexity: O(1)

Code 1

class Solution(object):
    def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """

        newStr =""

        for c in s: 
            if c.isalnum():
                newStr += c.lower()

        #print (newStr)
        return newStr == newStr[::-1]

Code 2

class Solution(object):
    def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        #Using two pointers
        left_ptr, right_ptr = 0, len(s)-1

        while left_ptr < right_ptr :
            while left_ptr < right_ptr and not self.isAlNum(s[left_ptr]):
                left_ptr += 1
            while left_ptr < right_ptr and not self.isAlNum(s[right_ptr]):
                right_ptr -= 1  
                
            #Check this first wheater it is same or not 
            if s[left_ptr].lower() != s[right_ptr].lower():
                return False
            
            left_ptr, right_ptr = left_ptr +1, right_ptr -1
        return True

    def isAlNum(self, c):
        # ASCII code base comparison
        return ('A'<=c<='Z' or 'a'<=c<='z' or '0'<=c<='9')