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

One way to solve this problem is to create new string with only alphanumeric symbols and then check if it is palindrome. However we need O(n) space for this. There is more subtle approach, using Two Pointers technique.

  1. Start with beg = 0 and end = len(s) - 1, the first and the last symbols of string s.
  2. Now, we are going to move iterator beg only to the right and iterator end only to the left. Let us move them, until we reach alphanumeric symbols, using isalnum() function.
  3. Compare these two symbols. We are happy, if they are equal, or it is the same letter in different capitalization, for example q and Q. How to check this case? Make both symbols capitalized, using .upper() and compare them.
  4. In opposite case, immidietly return False.
  5. If we reached the end of or program and we did not return False, then we need to return True.

Complexity: Time complexity is O(n), because we move beg only to the right and end only to the left, until they meet. Space complexity is O(1), we just use a couple of additional variables.

class Solution:
    def isPalindrome(self, s):
        beg, end = 0, len(s) - 1
        while beg <= end:
            while not s[beg].isalnum() and beg < end: beg += 1
            while not s[end].isalnum() and beg < end: end -= 1
            if s[beg] == s[end] or s[beg].upper() == s[end].upper():
                beg, end = beg + 1, end - 1
            else:
                return False
        return True

If you like the solution, you can upvote it on leetcode discussion section: Problem 0125