Valid Palindrome

The problem description can be found in LeetCode.

Approach

A string is a palindrome if s == reversed(s), so, for example, Anna is a palindrome, if we do a case insensitive comparison.

In contrast with the usual palindrome problem, this question asks us to only compare alphanumeric characters ([a-zA-Z0-9]).

This is a classic example of a Two Pointers algorithm.

We can start one pointer at the beginning (left one) and one on the end (right one). If the two characters are alphanumeric, we can compare them, otherwise, we move the pointers until there are two alphanumeric characters to compare.

In general, we can then interrupt our algorithm if the characters are different, otherwise move both pointers. We will continue until the two pointers meet.

Solution

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left, right = 0, len(s) - 1

        while left < right:
            if not self.is_alphanumeric(s[left]):
                left += 1
            elif not self.is_alphanumeric(s[right]):
                right -= 1
            else:
                if s[left].lower() != s[right].lower():
                    return False

                left += 1
                right -= 1

        return True

    def is_alphanumeric(self, char: str) -> bool:
        assert isinstance(char, str)
        assert len(char) == 1

        return "a" <= char <= "z" or "A" <= char <= "Z" or "0" <= char <= "9"

Note that the Python standard library offers the str.isalnum, which checks if all characters in the string are alphanumeric. So, we can rewrite the previous solution as:

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left, right = 0, len(s) - 1

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

                left += 1
                right -= 1

        return True

Complexity

• Time: $O(n)$
• Space: $O(1)$

Where $n$ is the length of the string s.