企业官网建设流程全解析

LeetCode 题解仓库实战：125 验证回文串的双指针解法与三语言实现

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

本篇基于 LeetCode 解题仓库（leetcode）中收录的 125 题解文档，系统讲解"验证回文串"这道经典字符串题：从回文判定与头尾双指针的核心思路出发，结合仓库内完整的 JavaScript、C++、Python 实现，剖析"非法字符跳过 + 大小写归一"这一关键过滤逻辑。读完后你可以独立写出 O(N) 时间、O(1) 空间的双指针回文判定代码，并理解各语言在字符合法性判断上的差异。

题目描述

LeetCode 125. Valid Palindrome（验证回文串）：

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

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

• 示例 1：输入"A man, a plan, a canal: Panama"，输出true
• 示例 2：输入"race a car"，输出false

该题在仓库中的原始文档位于 125.valid-palindrome.en.md，中文版题为 125.valid-palindrome.md，并已收录进 SUMMARY.md 的目录索引与 easy 难度题集。

前置知识与考察公司

前置知识（来自原文档 Pre-knowledge 小节）：

• 回文（Palindrome）：正读与反读完全相同的序列
• 双指针（Two Pointers）：本题采用头尾对向移动的头尾双指针

原文档列出的考察该题的公司包括：阿里、腾讯、百度、字节，以及 facebook、microsoft、uber、zenefits，可见这是各大厂高频的基础题。

核心思路：头尾双指针

这是一道考察回文判定的题目，也是最简单的形式——判断一个字符串是否是回文。针对它，可以使用头尾双指针：

• 初始化left = 0、right = n - 1，分别指向字符串首尾；
• 如果两个指针指向的字符相同，则同时向内移动（left++、right--），继续循环，直到两个指针相遇或交叉；
• 如果在移动前发现两个指针的字符不相同，直接判定为 false。

时间复杂度为 O(N)，空间复杂度为 O(1)。原文档用两个例子演示了判断过程：

以回文串"noon"为例，头尾指针成对配对成功，最终相遇：

以非回文串"abaa"为例，当left指向'b'、right指向'a'时配对失败（红叉），直接返回 false：

本小题的唯一"陷阱"在于：只考虑字母和数字字符。指针在移动过程中必须先跳过非法字符（空格、标点等），再比较大小写归一后的字符。这一点在三种语言的实现中都有对应处理，也是本题的关键点所在。

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; };

实现要点：

• isValid(c)手写字符判定：利用charCodeAt(0)拿到字符的 ASCII 码，判断是否落在0-9或a-z区间。之所以只判断小写区间，是因为入口处已对整串执行s = s.toLowerCase()归一化——先统一转小写，比较时就不必再做toLowerCase，避免每轮循环都调用字符串方法。
• 循环用continue跳过非法字符：指针停在非法字符上时不进入比较分支，直接内移一步，保证比较的一定是字母或数字。
• 返回值right <= left：循环因left >= right（指针相遇/交叉）正常退出时为 true；因break（字符不匹配）提前退出时right > left，返回 false。这一写法把"匹配失败 break"与"正常走完"两种出口统一成了同一个布尔判断。

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++ 版本的实现思路与 JavaScript 版一致，差异在于：

• 使用标准库函数isalnum判断字母数字，用tolower在比较时逐字符转小写，无需预处理整串；
• 用两个裸指针s1/e分别指向首尾，循环条件e > s1即"右指针仍在左指针右侧"；
• 空串显式提前返回 true（空字符串是有效回文）。

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++ 版逻辑完全一致。字符串单字符上可直接调用str.isalnum()与str.lower()，代码更简洁；返回right <= left的收尾技巧同样保留；
• isPalindrome2（语言特性法）：先用生成器表达式i for i in s if i.isalnum()过滤出全部字母数字字符，拼接后整体lower()，再用切片s[::-1]反转，直接比较s == s[::-1]。写法极简，但会构造过滤后的新字符串，空间开销不再是 O(1)，更适合面试白板之外的快速编码场景。

仓库中文版题解额外收录了 Java 实现，可作为第四种语言参考，其特点是用内层 while 循环"就地吸附"指针到下一个合法字符，避免continue分支：

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; } }

复杂度分析

• 时间复杂度：O(N)。每个字符最多被每个方向的指针访问一次，指针只进不退；
• 空间复杂度：O(1)。双指针方案只使用常数额外变量（Python 的isPalindrome2因生成新串例外，空间为 O(N)）。

小结

125 验证回文串是双指针模板题的起点，仓库题解的核心脉络可概括为三点：一是头尾双指针对向扫描，O(N) 完成全串配对检查；二是合法性过滤先行——指针停在非字母数字字符上时先跳过再比较，比较前统一小写（toLowerCase/tolower/lower()，或在入口一次性归一化）；三是出口统一——匹配失败break后以right <= left一个表达式区分"正常相遇"与"提前失败"两种结束方式。这套"过滤 + 对向比较"的骨架可直接复用到 5.longest-palindromic-substring、139.word-break 等其他回文类题目中，相关题解可继续在仓库 problems 目录 中检索。

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