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 125Easy要求给定一个字符串验证它是否是回文串只考虑字母和数字字符可以忽略字母的大小写。说明本题中我们将空字符串定义为有效的回文串。两个标准示例输入输出说明A man, a plan, a canal: Panamatrue忽略空格、冒号与大小写后为amanaplanacanalpanama正读反读一致race a carfalse忽略空格后为raceacar反读为racacear不一致需要特别注意题目隐含的三个处理规则字符过滤标点符号、空格等非字母数字字符一律跳过不参与比较大小写归一字母比较前统一转为小写或大写如A与a视为相等空串语义空字符串按题意是合法回文直接返回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 中也将其列为独立章节适合作为双指针入门的第一个练习。思路头尾双指针判定回文针对判断整串是否回文这一最简形式核心算法如下将输入统一转为小写处理大小写规则初始化左指针left 0、右指针right s.length - 1循环条件left right每一轮若左指针指向的字符不是字母或数字left跳过继续若右指针指向的字符不是字母或数字right--跳过继续两侧都是有效字符时进行比较不相同则直接判定失败相同则left、right--同时向中间收缩循环正常结束指针相遇或交叉则说明所有对称位置的字符均相等返回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 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; };JS 实现要点先统一toLowerCase()再通过字符码范围手工判定0-9与a-z避免依赖正则的性能开销遇到非法字符时用continue跳过。Cclass 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*指针而非下标方式遍历先判空串再进入循环。Pythonclass 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) 的额外空间。Javaclass 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考