【LeetCode】125. 验证回文串

一、题目描述

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

示例 1:

输入: "A man, a plan, a canal: Panama"
输出: true

示例 2:

输入: "race a car"
输出: false

二、解题思路 & 代码

2.1 直接取反比较

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

2.2 双指针（需新建数组）

class Solution:
    def isPalindrome(self, s: str) -> bool:
        s_list= [ch.lower() for ch in s if ch.isalnum()]
        sgood = "".join(s_list)  # 列表转为字符串
        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(|s|)，其中 |s| 是字符串 s 的长度
• 空间复杂度：O(|s|)

2.3 双指针（在原字符串上直接判断）

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

复杂度分析

• 时间复杂度：O(∣s∣)，其中 |s| 是字符串 s 的长度。
• 空间复杂度：O(1)。

参考：

1. LeetCode官方题解