首页 > itarticle > leetcode_valid palindrome

leetcode_valid palindrome

admin 11月 13, 2020 0

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. 双指针

两个指针分别指向字符串的首尾，查到符合要求的字符时就判断两者是否相同。具体实现过程如下：

class :
    def isPalindrome(self, s: str) -> bool:
        if not s:
            return True
        
        n = len(s)
        i, j = 0, n-1
        
        s = s.lower()
        while i<j:
            
            while i<n and not s[i].isalnum():
                i+=1
            while j>=0 and not s[j].isalnum():
                j-=1
            if i<=j and s[i] != s[j]:
                return False
            i+=1
            j-=1
                
        return True

2.翻转

判断翻转后的字符串与原来是是否一致，空间复杂度是 O(n) 。具体实现过程如下：

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