125. 验证回文串（简单）

Blind 75 › 125. 验证回文串（简单） （第 1 章）
文章工具

题目

给定一个字符串 s。先把它“清洗”一遍：所有大写字母换成小写，所有既不是字母、也不是数字的字符删掉。如果清洗后的串正着读和反着读完全一样，就返回 true；否则返回 false。

这里的“字母数字”包括 a~z、A~Z 和 0~9；标点、空格、符号都要在比较时忽略。

自造示例：s = "No lemon, no melon!" → 清洗后是 "nolemonnomelon"，正反读一样，返回 true。

再看：s = "Hello, World!" → 清洗后是 "helloworld"，反转后是 "dlrowolleh"，返回 false。

再看：s = " @# " → 清洗后是空串 ""，空串正反读相同，返回 true。

约束：长度 1 ≤ s.length ≤ 2 × 105；s 仅由可打印 ASCII 字符组成。

思路

一句话：左右两个指针从两端向中间靠，跳过非法字符后比较两个“有效字符”的小写形式。

最直白的做法：先遍历一遍，把字母数字挑出来并转小写，拼成一个新串 clean；再比较 clean 和它的反转串。这个思路完全正确，时间 O(n)，但要额外开一个 O(n) 的新串，而且要完整扫两遍。

关键观察：回文的核心是对称——第 i 个有效字符必须和第 倒数第 i 个有效字符相同。我们其实不需要把清洗后的串真的拼出来：从左右两端同时走，遇到标点、空格就跳过，遇到有效字符就转小写比较，一步到位。

于是选定相向双指针：左指针负责原串的开头，右指针负责原串的结尾；每次都先让两侧跳到最近的字母数字上，再比较。这样既不额外分配空间，又把“过滤”和“比较”合并成一次扫描。

解法

设 left = 0、right = s.length - 1，循环执行：

  1. left 向右移动，直到 s[left] 是字母或数字，或与 right 相遇。
  2. right 向左移动，直到 s[right] 是字母或数字，或与 left 相遇。
  3. 把两侧字符都转成小写比较；一旦不等，直接返回 false。
  4. 相等就让 left++、right--，继续检查下一对。
  5. 循环正常结束，说明所有对称位置都匹配，返回 true。

以 s

🔒

本篇为付费内容

您已阅读试读部分，购买后即可解锁全文。

⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。