[TwoPointer]125. Valid Palindrome

• 分类：String/TwoPointer
• 时间复杂度: O(n)
• 空间复杂度: O(1)

125. Valid Palindrome

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

Note: For the purpose of this problem, we define empty string as valid palindrome.

Example 1:

Input: "A man, a plan, a canal: Panama"
Output: true

Example 2:

Input: "race a car"
Output: false

代码：

class Solution:
    def isPalindrome(self, s: str) -> bool:
        start=0
        end=len(s)-1
        while start<end:
            while start<end and (not s[start].isalpha()) and (not s[start].isdigit()):
                start+=1
            while start<end and (not s[end].isalpha()) and (not s[end].isdigit()):
                end-=1
            if s[start].lower()!=s[end].lower():
                return False
            start+=1
            end-=1
        return True

讨论：

1. 一道一看就知道要用two pointer的题
2. 到bug free用了三步：

• 忘记最后的start+=1和end-=1(还以为是for循环呢orz)
• 忘了两个while中也要放start<end,不然就会出现越界问题
• 把while这里用了if