125. 验证回文串#

题目描述#

题目链接: LeetCode 125

如果在将所有大写字符转换为小写并移除所有非字母数字字符之后，正着读和反着读都一样的字符串，则它就是一个回文串。给定一个字符串 s，如果它是回文串，返回 true，否则返回 false。

示例：

1
输入：s = "A man, a plan, a canal: Panama"
2
输出：true
3
解释："amanaplanacanalpanama" 是回文串。

解题思路#

核心思想#

回文串对称比较，天然适合相向双指针：左指针指向开头、右指针指向结尾，跳过所有非字母数字字符后，比较两字符是否相等（忽略大小写）。若出现不等则不是回文串。

算法步骤#

left = 0, right = len(s) - 1
当 left < right：
- 跳过非字母数字：左指针右移直到 s[left].isalnum()，右指针左移直到 s[right].isalnum()
- 比较 s[left].lower() == s[right].lower()，不等则返回 False
- left += 1, right -= 1
返回 True

逐步举例#

s = "A man, a plan, a canal: Panama"

字符（原文）	处理	比较
`A` vs `a`	跳过空格和标点后，忽略大小写	`a == a` ✅
`m` vs `m`	—	✅
`a` vs `a`	—	✅
…	逐渐逼近中央	…
`P` vs `n` 前	—	最终全部对称 ✅

返回 true。

复杂度分析#

时间复杂度：O(n)，每个字符最多访问一次
空间复杂度：O(1)，只用了两个指针

代码实现#

1
class Solution:
2
    def isPalindrome(self, s: str) -> bool:
3
        left, right = 0, len(s) - 1
4
        while left < right:
5
            while left < right and not s[left].isalnum():
6
                left += 1
7
            while left < right and not s[right].isalnum():
8
                right -= 1
9
            if s[left].lower() != s[right].lower():
10
                return False
11
            left += 1
12
            right -= 1
13
        return True

1
import sys
2
from pathlib import Path
3

4
sys.path.insert(0, str(Path(__file__).parent))
5

6
import unittest
7

8
from solution import Solution
9

10

11
class Test125(unittest.TestCase):
12
    def test_example1(self):
13
        self.assertTrue(Solution().isPalindrome("A man, a plan, a canal: Panama"))
14

15
    def test_example2(self):
16
        self.assertFalse(Solution().isPalindrome("race a car"))
17

18
    def test_empty_space(self):
19
        self.assertTrue(Solution().isPalindrome(" "))
20

21
    def test_underscore(self):
22
        self.assertTrue(Solution().isPalindrome("ab_a"))
23

24

25
if __name__ == '__main__':
26
    unittest.main()