LeetCode | 125.验证回文串

这道题一开始的想法是把原字符串的非数字英文字符去掉，然后判断剩下的字符串是否为回文串即可，其中去掉非数字英文字符可以遍历一遍字符串依次处理，也可以用正则表达式，然后判断是否是回文串只需要两个指针，一头一尾，只要不相等就返回false，相等就两个指针靠近，直到两个指针重合或者相邻且所指字符相等即可

import re
class Solution(object):
    def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        ss = self.remove_non_alphanumeric(s)
        if len(ss) == 0:
            return True
        i, j = 0, len(ss) - 1
        while i <= j:
            if ss[i].lower() == ss[j].lower():
                i += 1
                j -= 1
                if i == j:
                    return True
                if i == j-1 and ss[i].lower() == ss[j].lower():
                    return True
            else:
                return False
        return True
    def remove_non_alphanumeric(self, s):
        # 使用正则表达式匹配非字母数字字符，并将其替换为空字符串
        return re.sub(r'[^a-zA-Z0-9]', '', s)

class Solution:
    def isPalindrome(self, s: str) -> bool:
        sgood = "".join(ch.lower() for ch in s if ch.isalnum())
        n = len(sgood)
        left, right = 0, n - 1
        
        while left < right:
            if sgood[left] != sgood[right]:
                return False
            left, right = left + 1, right - 1
        return True

但是这里还可以再继续优化空间复杂度，我们可以得到空间复杂度为

O

(

1

)

O(1)

O(1)的算法，直接在原字符串 s 上使用双指针。在移动任意一个指针时，需要不断地向另一指针的方向移动，直到遇到一个字母或数字字符，或者两指针重合为止。也就是说，我们每次将指针移到下一个字母字符或数字字符，再判断这两个指针指向的字符是否相同。

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

        return True