0125._valid_palindrome.md

125. Valid Palindrome

难度: Easy

刷题内容

原题连接

• https://leetcode.com/problems/valid-palindrome/description/

内容描述

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

解题方案

思路 1

就是比较reversed string 和原本的是否相等.

class Solution(object):
    def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        new = ''
        s = s.lower()
        
        for i in s:
            if '0' <= i <= '9' or 'a' <= i <= 'z':
                new += i
        return new == new[::-1]  

这样写更简单

class Solution:
    def isPalindrome(self, s):
        s = ''.join(e for e in s if e.isalnum()).lower()
        return s==s[::-1]

思路 2

或者用正则,详见re.sub()用法 瞬间beats 97.71%

class Solution(object):
    def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        s = re.sub('[^0-9a-zA-Z]+', '', s ).lower()
        return s == s[::-1]

思路 3

双指针in-place

时间复杂度还是O(n), 但是空间优化到了O(1)

class Solution(object):
    def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        l, r = 0, len(s)-1
        while l < r:
            while l < r and not s[l].isalnum():
                l += 1
            while l < r and not s[r].isalnum():
                r -= 1
            if s[l].lower() != s[r].lower():
                return False
            l +=1
            r -= 1
        return True