125.Valid Palindrome(验证回文串)

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

给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。

说明:本题中,我们将空字符串定义为有效的回文串。

思路:通过观察测试用例可以看到字符串中不只是包含字母和数字,所以要先提取出字母和数字,然后统一转换成小写或大写。之后比较字符串的正序和逆序可以判断是否符合要求

第一种方法

这里用到了Python中的isalnum()方法。它的作用是检测字符串是否由字母和数字组成

之后用到join()方法,它的作用是将序列中的元素以指定的字符连接生成一个新的字符串

所以提取出符合要求的字符串并转为小写为:

"".join([i for i in s if i.isalnum()]).lower()

完整的代码为:

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

Result:

Runtime: 56 ms, faster than 87.93% of Python3 online submissions for Valid Palindrome.
Memory Usage: 14 MB, less than 21.45% of Python3 online submissions for Valid Palindrome.

第二种方法

提取符合条件的字符串还可以利用Python的filter()。filter() 函数用于过滤序列,过滤掉不符合条件的元素,返回由符合条件元素组成的新列表。该接收两个参数,第一个为函数,第二个为序列,序列的每个元素作为参数传递给函数进行判,然后返回 True 或 False,最后将返回 True 的元素放到新列表中。

filter()语法:

filter(function, iterable)

所以提取出符合要求的字符串并转为小写为:

s = list(filter(str.isalnum, s.lower()))

完整的代码为:

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

Result:

Runtime: 52 ms, faster than 94.94% of Python3 online submissions for Valid Palindrome.
Memory Usage: 14.5 MB, less than 19.60% of Python3 online submissions for Valid Palindrome.

comments powered by Disqus