免费速建网站莆田seo
目录
一、问题描述
二、解题思路
三、代码
四、复杂度分析
一、问题描述
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。
二、解题思路
✅ 题目要求
判断一个字符串是否是回文串，忽略大小写并且忽略非字母数字字符。
✅ 解题关键点
-
忽略大小写 → 所以我们要用
tolower()把字符都转成小写。 -
只保留字母和数字 → 所以要用
isalnum()判断是否是有效字符（字母或数字）。 -
对称比较字符 → 使用双指针（从两端往中间走）判断字符是否一致。
✅ 举例说明：
示例："A man, a plan, a canal: Panama"
-
过滤掉空格、标点，只保留字母数字 →
"AmanaplanacanalPanama" -
转为小写 →
"amanaplanacanalpanama" -
判断是否正着读和反着读一致（是回文）→ ✅
✅ 双指针解法步骤（模拟过程）：
假设原字符串是 "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) | 使用双指针，不额外开辟空间（不存储新字符串） |