Valid Palindrome

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

For example, "A man, a plan, a canal: Panama"is a palindrome. "race a car"isnota palindrome.

Note: Have you consider that the string might be empty? This is a good question to ask during an interview.

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

首先把字串轉為全小寫,將字串裡面不是字母與數字的部分去, 反轉字串判斷與上一個步驟處理過的字串相等

class Solution(object):
    def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        ss=[i.lower() for i in s if i.isalnum()]
        return ss == ss[::-1]

回文必定是左右对称。所以双指针start/end分别向中间扫描比较。直到start/end对应的数字字母不同，返回false；或start/end相遇，返回true

class Solution(object):
    def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        """
        ss=[i.lower() for i in s if i.isalnum()]
        return ss == ss[::-1]
        """
        ss=[i.lower() for i in s if i.isalnum()]
        start = 0
        end = len(ss) - 1
        while start < end:
            if ss[start] != ss[end]:
                return False
            start += 1
            end -= 1
        return True