Valid Palindrome

Question

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

Challenge O(n) time without extra memory.

问题分析

1. empty string是否算palindrome
2. string中是否有除了alphanumeric的其他character
3. 大小写是否算同一个字母？

Thoughts

基本的2 pointer问题 不过这里遇到非alphanumeric的到跳过

Solution

class Solution:
    # @param {string} s A string
    # @return {boolean} Whether the string is a valid palindrome
    def isPalindrome(self, s):
        # Write your code here
        if not s:
            return True
        p1 = 0
        p2 = len(s) - 1
        s = s.lower()
        while p1 < p2:
            if s[p1] not in "abcdefghijklmnopqrstuvwxyz0123456789":
                p1 += 1
                continue
            if s[p2] not in "abcdefghijklmnopqrstuvwxyz0123456789":
                p2 -= 1
                continue
            if s[p1] == s[p2]:
                p1 += 1
                p2 -= 1
            else:
                return False
        return True