125. 验证回文串
题目描述
输入一个字符串 s。先删掉其中所有不是字母或数字的字符，再把大写字母全部换成小写。
如果处理后的字符串从左往右读和从右往左读完全相同，它就是回文串。
s 是回文串时返回 true，否则返回 false。处理后为空串也算回文。
示例 1
输入：s = "A man, a plan, a canal: Panama" 输出：true
解释：处理后得到 amanaplanacanalpanama，是回文。
示例 2
输入：s = "race a car" 输出：false
解释：处理后得到 raceacar，反过来读不同。
示例 3
输入：s = " " 输出：true
解释：去掉空格后是空串，空串是回文。
数据范围
1 <= s.length <= 2 * 10^5s只含可打印的 ASCII 字符。
解题思路：原地双指针
回文的定义是第 k 个有效字符等于倒数第 k 个有效字符。用左右两个指针从两端向中间走：先各自跳过非字母数字字符，再比较两个字符的小写形式。只要有一对不同就能立刻返回 false；两指针相遇说明所有对称位置都相同。这样不需要额外构造清洗后的字符串。
为什么正确
每轮开始时，s[:i] 与 s[j+1:] 中的有效字符已经两两对称匹配。
复杂度分析
时间 O(n)，每个字符最多被一个指针经过一次；额外空间 O(1)。
易错点
跳过非字母数字字符的内层循环也要带上 i < j 条件，否则全是标点时指针会越界；另外数字也是有效字符，不能只判断字母。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def isPalindrome(self, s: str) -> bool:
i, j = 0, len(s) - 1
while i < j:
while i < j and not s[i].isalnum():
i += 1
while i < j and not s[j].isalnum():
j -= 1
if s[i].lower() != s[j].lower():
return False
i, j = i + 1, j - 1
return Trueclass Solution {
public boolean isPalindrome(String s) {
int i = 0, j = s.length() - 1;
while (i < j) {
while (i < j && !Character.isLetterOrDigit(s.charAt(i))) {
i++;
}
while (i < j && !Character.isLetterOrDigit(s.charAt(j))) {
j--;
}
if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j))) {
return false;
}
i++; j--;
}
return true;
}
}class Solution {
public:
bool isPalindrome(string s) {
int i = 0, j = (int)s.size() - 1;
while (i < j) {
while (i < j && !isalnum((unsigned char)s[i])) {
i++;
}
while (i < j && !isalnum((unsigned char)s[j])) {
j--;
}
if (tolower(s[i]) != tolower(s[j])) {
return false;
}
i++; j--;
}
return true;
}
};func isAlnum(c byte) bool {
return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9')
}
func isPalindrome(s string) bool {
i, j := 0, len(s)-1
for i < j {
for i < j && !isAlnum(s[i]) {
i++
}
for i < j && !isAlnum(s[j]) {
j--
}
if unicode.ToLower(rune(s[i])) != unicode.ToLower(rune(s[j])) {
return false
}
i, j = i+1, j-1
}
return true
}var isPalindrome = function(s) {
const ok = c => /[a-zA-Z0-9]/.test(c);
let i = 0, j = s.length - 1;
while (i < j) {
while (i < j && !ok(s[i])) {
i++;
}
while (i < j && !ok(s[j])) {
j--;
}
if (s[i].toLowerCase() !== s[j].toLowerCase()) {
return false;
}
i++; j--;
}
return true;
};function isPalindrome(s: string): boolean {
const ok = (c: string) => /[a-zA-Z0-9]/.test(c);
let i = 0, j = s.length - 1;
while (i < j) {
while (i < j && !ok(s[i])) {
i++;
}
while (i < j && !ok(s[j])) {
j--;
}
if (s[i].toLowerCase() !== s[j].toLowerCase()) {
return false;
}
i++; j--;
}
return true;
}其他解法
过滤后反转比较写法简单，占 O(n) 空间；原地双指针边跳过边比较，只用 O(1) 空间，还能提前返回。
解法 2：过滤后反转比较 时间 O(n)，空间 O(n)
先遍历一遍，只保留字母和数字并转成小写，得到新字符串 t。再把 t 反转，判断反转后是否与 t 相等。
把“清洗”和“判断回文”拆成两步，代码最短，不容易写错。需要 O(n) 额外空间，且即使首尾就不同也要先处理完整个字符串。
class Solution:
def isPalindrome(self, s: str) -> bool:
t = [c.lower() for c in s if c.isalnum()]
return t == t[::-1]class Solution {
public boolean isPalindrome(String s) {
StringBuilder sb = new StringBuilder();
for (char c : s.toCharArray()) {
if (Character.isLetterOrDigit(c)) sb.append(Character.toLowerCase(c));
}
String t = sb.toString();
return t.equals(sb.reverse().toString());
}
}class Solution {
public:
bool isPalindrome(string s) {
string t;
for (char c : s) {
if (isalnum((unsigned char)c)) t += (char)tolower((unsigned char)c);
}
string r(t.rbegin(), t.rend());
return t == r;
}
};func isPalindrome(s string) bool {
t := []byte{}
for i := 0; i < len(s); i++ {
c := s[i]
if c >= 'A' && c <= 'Z' {
c += 'a' - 'A'
}
if (c >= 'a' && c <= 'z') || (c >= '0' && c <= '9') {
t = append(t, c)
}
}
r := make([]byte, len(t))
for i := range t {
r[len(t)-1-i] = t[i]
}
return string(t) == string(r)
}var isPalindrome = function(s) {
const t = s.toLowerCase().replace(/[^a-z0-9]/g, '');
return t === t.split('').reverse().join('');
};function isPalindrome(s: string): boolean {
const t = s.toLowerCase().replace(/[^a-z0-9]/g, '');
return t === t.split('').reverse().join('');
}