Valid Palindrome

Patrick Leaton
Published: March 5, 2021, 11:50 p.m.
Problem Description

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Note: For the purpose of this problem, we define empty string as valid palindrome.

Example 1:

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

Example 2:

Input: "race a car"
Output: false

 

Constraints:

  • s consists only of printable ASCII characters.

 

Description taken from https://leetcode.com/problems/valid-palindrome/.

Problem Solution

#O(N) Time, O(1) Space
class Solution:
    def isPalindrome(self, s: str) -> bool:
        letters_numbers = 'abcdefghijklmnopqrstuvwxyz0123456789'
        left = 0
        right = len(s) -1
        s = s.lower()
        while left < right:
            if s[left] != s[right]:
                if s[left] not in letters_numbers:
                    left += 1
                elif s[right] not in letters_numbers:
                    right -= 1
                else:
                    return False
            else:
                left +=1
                right -=1
        return True

Problem Explanation

Similar to a traditional palindrome problem, we can solve this question by using two pointers.  However, the only difference is instead of marking the palindrome as false when there is a mismatch between two characters, we will now be marking the palindrome as false if there is a mismatch between characters and the mismatched character is alphanumeric.

We are only looking for alphanumeric characters which are letters and digits, so we will create a reference string that holds all the letters and digits we may see. We could also use the built-in, isalnum() function for this but this is how we would do it manually.

        letters_numbers = 'abcdefghijklmnopqrstuvwxyz0123456789'

 

 We will then initialize a left and right pointer which we will use to compare the characters at both ends of the string moving inward.

        left = 0
        right = len(s) -1

 

Since the validation is not case-sensitive according to the description, we will convert the string to lowercase.

        s = s.lower()

 

While the left and the right pointers haven't overlapped, we still have characters to compare.

        while left < right:

 

If our left and right pointers do not match, we will check If they are letters or numbers.  If they are not, then we will move whichever pointer had the special character.

            if s[left] != s[right]:
                if s[left] not in letters_numbers:
                    left += 1
                elif s[right] not in letters_numbers:
                    right -= 1

 

If a mismatched character is a letter or number, we return false since the string is not a valid palindrome.

                else:
                    return False

 

Otherwise, if there wasn't a mismatch in characters we will move both pointers inward so that we can check the next two characters.

            else:
                left +=1
                right -=1

 

If the pointers overlapped and we never returned false, then each character matched up on the opposing end of the string so we will return true.

        return True