125. 验证回文串

目录

一、问题描述

二、解题思路

三、代码

四、复杂度分析

---

一、问题描述

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

二、解题思路

✅ 题目要求

判断一个字符串是否是回文串，忽略大小写并且忽略非字母数字字符。

---

✅ 解题关键点

1. 忽略大小写 → 所以我们要用 tolower() 把字符都转成小写。

2. 只保留字母和数字 → 所以要用 isalnum() 判断是否是有效字符（字母或数字）。

3. 对称比较字符 → 使用双指针（从两端往中间走）判断字符是否一致。

---

✅ 举例说明：

示例："A man, a plan, a canal: Panama"

1. 过滤掉空格、标点，只保留字母数字 → "AmanaplanacanalPanama"

2. 转为小写 → "amanaplanacanalpanama"

3. 判断是否正着读和反着读一致（是回文）→ ✅

---

✅ 双指针解法步骤（模拟过程）：

假设原字符串是 "ab#cB!a"
过滤后变成 "abcba"

• left = 0，指向 'a'

• right = 6，指向 'a'
  → 相等，继续

• left = 1，指向 'b'

• right = 5，指向 'B' → 转成小写后也等，继续

• left = 2，指向 'c'

• right = 4，指向 'c' → 相等，继续

最终 left >= right，说明每一对字符都匹配 → ✅ 是回文

三、代码

class Solution {
public:bool isPalindrome(string s) {int left = 0;                  // 左指针，指向字符串开头int right = s.size() - 1;     // 右指针，指向字符串末尾while (left < right) {// 如果左指针不是字母或数字，向右移动while (left < right && !isalnum(s[left])) ++left;// 如果右指针不是字母或数字，向左移动while (left < right && !isalnum(s[right])) --right;// 对比当前字符（都转成小写），不相等则不是回文if (tolower(s[left]) != tolower(s[right])) {return false;}// 移动两个指针继续比较++left;--right;}return true;  // 成功通过所有对比，说明是回文}
};

四、复杂度分析

项目	复杂度	说明
⏱ 时间复杂度	O(n)	每个字符最多遍历一次
🧠 空间复杂度	O(1)	使用双指针，不额外开辟空间（不存储新字符串）