leetcode-125 | 验证回文串

125. 验证回文串（Valid Palindrome）

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。

示例1：
输入: “A man, a plan, a canal: Panama”
输出: true
示例2：
输入: “race a car”
输出: false

思路

方法一： 去除其余非字母，然后双指针判断

去除空格、逗号、冒号等，然后用两个指针i，j来遍历判断。

class Solution(object):
    def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        s = s.lower()
        li=''
        i, j= 0, 0
        while i<len(s):
            if s[i].isalpha() or s[i].isdigit():
               li+=s[i]
            i+=1
        k = len(li)-1
        while j<=k:
            if li[j]!=li[k]:
                return False
            else:
                j+=1
                k-=1
        return True

结果：
执行用时 : 396 ms, 在Valid Palindrome的Python提交中击败了13.90% 的用户
内存消耗 : 13.2 MB, 在Valid Palindrome的Python提交中击败了33.37% 的用户

提交时间	状态	执行用时	内存消耗	语言
几秒前	通过	396 ms	13.2MB	python

方法二：优化方法一

方法一中是先得到无特殊字符的字符串，然后，我们定义两个指针i，j分别从前到后扫描处理后的字符串。
但是，其实可以采用更简单的方式判断。因为这是一个字符串，如果是回文串，那么正向和反向的字母相同，那么我们可以直接反向处理后的字符串，然后==判断即可。

class Solution:
    def isPalindrome(self, s: str) -> bool:
        i = 0
        li = ""
        while i<len(s):
            if s[i].isalnum():
                li+=s[i]
            i+=1
        li = li.lower()
        return li==li[::-1]

结果：
执行用时 : 88 ms, 在Valid Palindrome的Python3提交中击败了55.73% 的用户
内存消耗 : 13.4 MB, 在Valid Palindrome的Python3提交中击败了81.85% 的用户

提交时间	状态	执行用时	内存消耗	语言
几秒前	通过	88 ms	13.4MB	python

### 方法三：优化方法一 使用python的内建函数filter

class Solution:
    def isPalindrome(self, s: str) -> bool:
        t = "".join(filter(str.isalnum, s)).lower()
        return t == t[::-1]

结果：
执行用时 : 64 ms, 在Valid Palindrome的Python3提交中击败了98.88% 的用户
内存消耗 : 13.9 MB, 在Valid Palindrome的Python3提交中击败了51.55% 的用户

提交时间	状态	执行用时	内存消耗	语言
几秒前	通过	64 ms	13.9MB	python