Valid palindrome: two pointers that skip non-alphanumerics

Coding Challenges
, ,
1

Problem. Return True if a string reads the same forward and backward after lowercasing and removing non-alphanumeric characters.

This is the classic filtered two-pointer scan pattern.

Examples:

  • s = "A man, a plan, a canal: Panama" → True
  • s = "race a car" → False
  • s = " " → True

Solution. Use one pointer from each end. Skip characters that do not matter and compare lowercase versions of the remaining characters.

def is_palindrome(s):
    left = 0
    right = len(s) - 1

    while left < right:
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1

    return True

O(n) time, O(1) extra space.

Gotchas.

  • Filtering into a brand-new string is acceptable but uses extra memory.
  • Only alphanumeric characters participate in the palindrome check.
  • An empty filtered string counts as a palindrome.

Run: Valid Palindrome