企业官网建设流程全解析

LeetCode 125 验证回文串：头尾双指针解法全解（含 JS/C++/Python/Java 多语言实现）

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode

本篇技术指南以 leetcode 题解仓库中的 125. 验证回文串题解 为核心，系统讲解"只考虑字母和数字、忽略大小写"的回文串验证问题：从回文与双指针的前置知识出发，推导出头尾双指针的 O(N) 算法，结合仓库中的流程示意图逐字符拆解判断过程，并给出 JavaScript、C++、Python、Java 四种语言的完整可运行实现与复杂度分析。读完本文，你将掌握"左右端点指针"这一双指针基础套路的判定写法，并能够举一反三解决同类字符串回文问题。

题目描述与关键约定

原题（LeetCode 125，Easy）要求：

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。

两个标准示例：

需要特别注意题目隐含的三个处理规则：

1. 字符过滤：标点符号、空格等非字母数字字符一律跳过，不参与比较；
2. 大小写归一：字母比较前统一转为小写（或大写），如'A'与'a'视为相等；
3. 空串语义：空字符串按题意是合法回文，直接返回true。

这三个规则也正是后续多语言实现中字符判定函数与大小写归一化的直接来源。

前置知识：回文与双指针

本题在仓库的 字符串问题专题 中被归入"回文"分类。该专题对回文的定义是：回文串就是一个正读和反读都一样的字符串，比如level、noon等，并明确指出：

判断是否回文的通用方法是首尾双指针，具体可以见下方 125 号题目。

这与 91 天学算法·双指针专题 中的"左右端点指针"分类完全对应。该专题将双指针分为三类：

• 快慢指针（两个指针步长不同，典型如链表判环）；
• 左右端点指针（两个指针分别指向头尾并向中间移动，步长不确定）；
• 固定间距指针（两个指针间距与步长均相同，典型如固定窗口滑动）。

125 题正是"左右端点指针"的入门模板题，其通用框架为：

l = 0 r = n - 1 while l < r if 找到了 return 找到的值 if 一定条件1 l += 1 else if 一定条件2 r -= 1 return 没找到

理解这一框架后，125 题就是在"比较头尾字符"这一判断逻辑上套用了相同的指针收缩模式。仓库的 README.md 将该题收录于基础题单（第 213 行），SUMMARY.md 中也将其列为独立章节，适合作为双指针入门的第一个练习。

思路：头尾双指针判定回文

针对"判断整串是否回文"这一最简形式，核心算法如下：

1. 将输入统一转为小写（处理大小写规则）；
2. 初始化左指针left = 0、右指针right = s.length - 1；
3. 循环条件left < right，每一轮：
   • 若左指针指向的字符不是字母或数字，left++跳过，继续；
   • 若右指针指向的字符不是字母或数字，right--跳过，继续；
   • 两侧都是有效字符时进行比较：不相同则直接判定失败；相同则left++、right--同时向中间收缩；
4. 循环正常结束（指针相遇或交叉）则说明所有对称位置的字符均相等，返回true。

该算法最多完整扫描字符串一次，时间复杂度为O(N)，且只使用常数个额外变量，空间复杂度为O(1)。

流程示意："noon"（回文串，返回 true）

仓库中的示意图 125.valid-palindrome-1.png 展示了字符串noon的完整判断过程：

• 初始：左指针指向s[0]='n'，右指针指向s[3]='n'，比较相等；
• 第一次收缩：左指针指向s[1]='o'，右指针指向s[2]='o'，比较相等；
• 指针继续向中间移动直至交叉（right <= left），所有对称位置均相等，判定为回文，返回true。

流程示意："abaa"（非回文串，返回 false）

仓库中的示意图 125.valid-palindrome-2.png 展示了字符串abaa的判断过程：

• 初始：左指针指向s[0]='a'，右指针指向s[3]='a'，比较相等；
• 收缩后：左指针指向s[1]='b'，右指针指向s[2]='a'，二者不相等（图中以红色叉号标记），循环中断；
• 由于存在不对称字符，判定为非回文，返回false。

两图对比可以清晰看出：双指针解法在遇到第一对不相等字符时即可提前终止，无需处理剩余字符，这是该算法的高效之处。

关键点解析

• 双指针：用左右两个指针从两端向中间扫描，将"逐位比较"的时间开销控制在 O(N)；
• 字符合法性判定：每轮比较前必须先跳过非字母数字字符，否则"A man..."这类含空格与标点的输入会得到错误结论；
• 大小写归一：统一转小写后再比较，避免'A'与'a'被误判为不同；
• 循环终止条件：使用while (left < right)，跳出后通过right <= left判断是否完整走完（对应空串与奇数长度串的情况）。

多语言实现

原题解支持 JS、C++、Python、Java 四种语言，以下代码均可在对应 LeetCode 环境中直接运行。

JavaScript

/* * @lc app=leetcode id=125 lang=javascript * * [125] Valid Palindrome */ // 只处理英文字符（题目忽略大小写，我们前面全部转化成了小写，因此这里我们只判断小写）和数字 function isValid(c) { const charCode = c.charCodeAt(0); const isDigit = charCode >= "0".charCodeAt(0) && charCode <= "9".charCodeAt(0); const isChar = charCode >= "a".charCodeAt(0) && charCode <= "z".charCodeAt(0); return isDigit || isChar; } /** * @param {string} s * @return {boolean} */ var isPalindrome = function (s) { s = s.toLowerCase(); let left = 0; let right = s.length - 1; while (left < right) { if (!isValid(s[left])) { left++; continue; } if (!isValid(s[right])) { right--; continue; } if (s[left] === s[right]) { left++; right--; } else { break; } } return right <= left; };

JS 实现要点：先统一toLowerCase()，再通过字符码范围手工判定0-9与a-z，避免依赖正则的性能开销；遇到非法字符时用continue跳过。

C++

class Solution { public: bool isPalindrome(string s) { if (s.empty()) return true; const char* s1 = s.c_str(); const char* e = s1 + s.length() - 1; while (e > s1) { if (!isalnum(*s1)) {++s1; continue;} if (!isalnum(*e)) {--e; continue;} if (tolower(*s1) != tolower(*e)) return false; else {--e; ++s1;} } return true; } };

C++ 实现要点：直接复用<cctype>标准库的isalnum（字母或数字判定）与tolower（转小写），以const char*指针而非下标方式遍历，先判空串再进入循环。

Python

class Solution: def isPalindrome(self, s: str) -> bool: left, right = 0, len(s) - 1 while left < right: if not s[left].isalnum(): left += 1 continue if not s[right].isalnum(): right -= 1 continue if s[left].lower() == s[right].lower(): left += 1 right -= 1 else: break return right <= left def isPalindrome2(self, s: str) -> bool: """ 使用语言特性进行求解 """ s = ''.join(i for i in s if i.isalnum()).lower() return s == s[::-1]

Python 给出两种写法：isPalindrome与 JS/C++ 同构，利用字符串的isalnum()与lower()方法；isPalindrome2则利用语言特性——先用生成器过滤出所有字母数字并统一小写，再通过s[::-1]反转后与自身比较，代码更简洁，代价是需要 O(N) 的额外空间。

Java

class Solution { public boolean isPalindrome(String s) { int n = s.length(); int left = 0, right = n - 1; while (left < right) { while (left < right && !Character.isLetterOrDigit(s.charAt(left))) { ++left; } while (left < right && !Character.isLetterOrDigit(s.charAt(right))) { --right; } if (left < right) { if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) { return false; } ++left; --right; } } return true; } }

Java 实现要点：使用Character.isLetterOrDigit与Character.toLowerCase两个静态方法完成判定与归一化；内层循环同样以left < right作为越界保护，避免指针越界。

复杂度分析

• 时间复杂度：O(N)——双指针单次遍历，最坏情况下每个字符被访问一次，比较与跳过均为常数时间；
• 空间复杂度：O(1)——除输入字符串外仅使用left、right两个指针变量（Java 版额外无数组，Python 的isPalindrome2因创建新字符串为 O(N)，本题解中以 O(1) 版本为主）。

边界情况与进阶思考

• 空串：直接满足题意返回true，各实现中的while (left < right)天然覆盖此情形；
• 全为符号的串（如"!!!"）：所有字符被跳过，指针最终相遇，返回true，符合题意"空串视为回文"的扩展；
• 奇数长度串（如"abcba"）：中位字符无需与任何字符比较，指针相遇即结束，不影响结果；
• 大小写混合（如"Aba"）：归一化后a与A视为相等，返回true。

本题是"左右端点指针"套路的基石题。掌握后，建议顺藤摸瓜阅读仓库中同一分类下的进阶题目：

• 5. 最长回文子串——由"判定"升级为"寻找"，核心思想是"扩展"；
• 131. 分割回文串——回文判定与回溯的组合应用；
• 516. 最长回文子序列——回文问题的动态规划形式；
• 1332. 删除回文子序列——对"回文"性质的巧妙利用。

参考与延伸阅读

• 125. 验证回文串（仓库原题解）
• 字符串问题专题：回文一节
• 91 天学算法·双指针专题：左右端点指针
• 双指针题解示意图：noon 与 abaa

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode