0125. Valid Palindrome

Problem Category:: Two pointer methods Neetcode Category:: Two Pointers

https://leetcode.com/problems/valid-palindrome/

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

• Case insensitive. Ignore non alphanumeric characters

Thoughts

• Going middle out or ends in for a palindrome will encounter the same letters each iteration
  • This suits a Two Pointers approach
• Since the string can have non-alphanumerics, it’s hard to go middle out

Optimal

Two pointers

Traverse from the ends towards the middle

• We reach the middle when the first pointer passes by the second pointer
• Keep traversing on a side if we encounter non-alphanumeric characters
• Ignore case differences

Python solution

class Solution:
    def isPalindrome(self, s: str) -> bool:
        c1 = 0
        c2 = len(s) - 1
 
        while c1 < c2:
            while not s[c1].isalnum():
                c1 += 1
            while not s[c2].isalnum():
                c2 -= 1
 
            if s[c1].lower() != s[c2].lower():
                return False
        
            c1 += 1
            c2 -= 1
        
        return True

• Time complexity: $O(n)$
• Space complexity: $O(1)$. No extra space used