拓冰网站定制 
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 appleetcode id125 langjavascript * * [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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 题解仓库实战：125 验证回文串的双指针解法与三语言实现
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 appleetcode id125 langjavascript * * [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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考