Valid Palindrome验证回文串全面解析反转字符串与双指针两种解法及多语言实现【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本文围绕 LeetCode 125「Valid Palindrome验证回文串」展开结合本仓库 articles/is-palindrome.md 的完整讲义与 python/、c/、go/ 等多语言源码实现系统讲解「反转字符串比较」与「双指针原地判断」两种解法、各自的复杂度特征以及最常见的两个踩坑点。读完本文你将掌握字母数字字符过滤、大小写归一化与双指针向内收敛这三类核心技巧并能直接套用到Valid Palindrome II、Palindrome Linked List等同类回文题目中。问题回顾与前置知识题目要求给定一个字符串s判断它是否为回文串——但只考虑字母和数字字符且忽略大小写空字符串视为有效回文。例如A man, a plan, a canal: Panama应返回true而race a car返回false。在动手编码前需要先具备以下三项基础能力双指针Two Pointers从字符串两端各取一个指针向中间移动逐个比较字符这是本题两种主流解法之一的核心思想字符串处理String Manipulation包括过滤字符、大小写转换与字符串反转等基础操作字符分类Character Classification能够识别一个字符是字母/数字alphanumeric还是标点、空格等非字母数字字符。仓库中 hints/is-palindrome.md 也给出了官方提示推荐以O(n)时间、O(1)空间为目标求解其中n是输入字符串的长度暴力做法复制字符串、反转、比较虽然也是O(n)但会额外占用O(n)空间。解法一反转字符串Reverse String直觉判断回文时我们真正关心的只有字母和数字其余字符空格、标点、特殊符号都可以忽略。因此可以先构建一个只含字母数字、且全部转为小写的清洗后字符串这样问题就退化为一个极简的判定字符串与它自身反转后完全相等即为回文。算法步骤创建一个空字符串newStr遍历输入字符串中的每个字符c若c是字母或数字转为小写后追加到newStr比较newStr与它的反转newStr[::-1]相等则返回true否则返回false。多语言实现Pythonclass Solution: def isPalindrome(self, s: str) - bool: newStr for c in s: if c.isalnum(): newStr c.lower() return newStr newStr[::-1]Javapublic class Solution { public boolean isPalindrome(String s) { StringBuilder newStr new StringBuilder(); for (char c : s.toCharArray()) { if (Character.isLetterOrDigit(c)) { newStr.append(Character.toLowerCase(c)); } } return newStr.toString().equals(newStr.reverse().toString()); } }Cclass Solution { public: bool isPalindrome(string s) { string newStr ; for (char c : s) { if (isalnum(c)) { newStr tolower(c); } } return newStr string(newStr.rbegin(), newStr.rend()); } };JavaScriptclass Solution { /** * Check if a character is alphanumeric * param {char} char * return {boolean} */ isAlphanumeric(char) { return ( (char a char z) || (char A char Z) || (char 0 char 9) ); } /** * param {string} s * return {boolean} */ isPalindrome(s) { let newStr ; for (let c of s) { if (this.isAlphanumeric(c)) { newStr c.toLowerCase(); } } return newStr newStr.split().reverse().join(); } }C#public class Solution { public bool IsPalindrome(string s) { string newStr ; foreach (char c in s) { if (char.IsLetterOrDigit(c)) { newStr char.ToLower(c); } } return newStr new string(newStr.Reverse().ToArray()); } }Gofunc isPalindrome(s string) bool { newStr : for _, c : range s { if (a c c z) || (0 c c 9) { newStr string(c) } else if A c c Z { newStr string(c a - A) } } reversedStr : reverse(newStr) return newStr reversedStr } func reverse(s string) string { runes : []rune(s) n : len(runes) for i : 0; i n/2; i { runes[i], runes[n-1-i] runes[n-1-i], runes[i] } return string(runes) }Kotlinclass Solution { fun isPalindrome(s: String): Boolean { var newStr for (c in s) { if (c.isLetterOrDigit()) { newStr c.lowercaseChar() } } return newStr newStr.reversed() } }Swiftclass Solution { func isPalindrome(_ s: String) - Bool { var newStr for c in s { if c.isLetter || c.isNumber { newStr.append(c.lowercased()) } } return newStr String(newStr.reversed()) } }Rustimpl Solution { pub fn is_palindrome(s: String) - bool { let new_str: Vecu8 s .bytes() .filter(|b| b.is_ascii_alphanumeric()) .map(|b| b.to_ascii_lowercase()) .collect(); new_str new_str.iter().copied().rev().collect::Vecu8() } }复杂度分析时间复杂度$O(n)$需要完整遍历一次字符串做过滤再遍历一次做反转比较空间复杂度$O(n)$需要额外的newStr及其反转副本存储清洗后的字符。仓库源码佐证仓库 python/0125-valid-palindrome.py 的实现与讲义完全一致仅在字符判定上使用a.isalpha() or a.isdigit()显式拆分字母与数字判断class Solution: def isPalindrome(self, s: str) - bool: new for a in s: if a.isalpha() or a.isdigit(): new a.lower() return (new new[::-1])此外rust/0125-valid-palindrome.rs 采用了更函数式的管道写法——用filtermap完成过滤与转小写后收集为Vecchar再通过首尾对称下标比较typescript/0125-valid-palindrome.ts 则直接用正则/[^A-Za-z0-9]/g一次性剔除所有非字母数字字符并转小写。可见同一思路在不同语言下可以演化出多种等价实现但时间复杂度与空间复杂度量级不变。解法二双指针Two Pointers直觉反转字符串解法简洁直观但代价是额外的 $O(n)$ 空间。双指针解法可以完全在原字符串上原地判断一个指针l从字符串开头出发另一个指针r从末尾出发两者不断向内移动跳过所有非字母数字字符当两个指针都落在有效字符上时就按小写形式比较。只要出现一次不相等即可判定不是回文。这样既避免了额外空间逻辑也同样简单高效。算法步骤初始化两个指针l指向字符串起始位置r指向字符串末尾位置。当l r时循环l持续前移直到指向字母数字字符r持续后移直到指向字母数字字符比较l与r处的小写字符若不相等直接返回false两个指针同时向内移动l 1、r - 1。循环结束仍未发现不匹配返回true。多语言实现Pythonclass Solution: def isPalindrome(self, s: str) - bool: l, r 0, len(s) - 1 while l r: while l r and not self.alphaNum(s[l]): l 1 while r l and not self.alphaNum(s[r]): r - 1 if s[l].lower() ! s[r].lower(): return False l, r l 1, r - 1 return True def alphaNum(self, c): return (ord(A) ord(c) ord(Z) or ord(a) ord(c) ord(z) or ord(0) ord(c) ord(9))Javapublic class Solution { public boolean isPalindrome(String s) { int l 0, r s.length() - 1; while (l r) { while (l r !alphaNum(s.charAt(l))) { l; } while (r l !alphaNum(s.charAt(r))) { r--; } if (Character.toLowerCase(s.charAt(l)) ! Character.toLowerCase(s.charAt(r))) { return false; } l; r--; } return true; } public boolean alphaNum(char c) { return (c A c Z || c a c z || c 0 c 9); } }Cclass Solution { public: bool isPalindrome(string s) { int l 0, r s.length() - 1; while (l r) { while (l r !alphaNum(s[l])) { l; } while (r l !alphaNum(s[r])) { r--; } if (tolower(s[l]) ! tolower(s[r])) { return false; } l; r--; } return true; } bool alphaNum(char c) { return (c A c Z || c a c z || c 0 c 9); } };JavaScriptclass Solution { /** * param {string} s * return {boolean} */ isPalindrome(s) { let l 0, r s.length - 1; while (l r) { while (l r !this.alphaNum(s[l])) { l; } while (r l !this.alphaNum(s[r])) { r--; } if (s[l].toLowerCase() ! s[r].toLowerCase()) { return false; } l; r--; } return true; } /** * param {char} c * return {boolean} */ alphaNum(c) { return ( (c A c Z) || (c a c z) || (c 0 c 9) ); } }C#public class Solution { public bool IsPalindrome(string s) { int l 0, r s.Length - 1; while (l r) { while (l r !AlphaNum(s[l])) { l; } while (r l !AlphaNum(s[r])) { r--; } if (char.ToLower(s[l]) ! char.ToLower(s[r])) { return false; } l; r--; } return true; } public bool AlphaNum(char c) { return (c A c Z || c a c z || c 0 c 9); } }Gofunc isPalindrome(s string) bool { l, r : 0, len(s)-1 for l r { for l r !isAlphaNum(rune(s[l])) { l } for r l !isAlphaNum(rune(s[r])) { r-- } if unicode.ToLower(rune(s[l])) ! unicode.ToLower(rune(s[r])) { return false } l r-- } return true } func isAlphaNum(c rune) bool { return unicode.IsLetter(c) || unicode.IsDigit(c) }Kotlinclass Solution { fun isPalindrome(s: String): Boolean { var l 0 var r s.length - 1 while (l r) { while (l r !s[l].isLetterOrDigit()) { l } while (r l !s[r].isLetterOrDigit()) { r-- } if (s[l].lowercase() ! s[r].lowercase()) { return false } l r-- } return true } }Swiftclass Solution { func isPalindrome(_ s: String) - Bool { let chars Array(s) var l 0, r chars.count - 1 while l r { while l r !isAlphaNum(chars[l]) { l 1 } while r l !isAlphaNum(chars[r]) { r - 1 } if chars[l].lowercased() ! chars[r].lowercased() { return false } l 1 r - 1 } return true } private func isAlphaNum(_ c: Character) - Bool { return c.isLetter || c.isNumber } }Rustimpl Solution { pub fn is_palindrome(s: String) - bool { let s s.as_bytes(); let (mut l, mut r) (0i32, s.len() as i32 - 1); while l r { while l r !s[l as usize].is_ascii_alphanumeric() { l 1; } while r l !s[r as usize].is_ascii_alphanumeric() { r - 1; } if s[l as usize].to_ascii_lowercase() ! s[r as usize].to_ascii_lowercase() { return false; } l 1; r - 1; } true } }复杂度分析时间复杂度$O(n)$每个字符最多被指针访问一次空间复杂度$O(1)$只使用两个指针不依赖输入长度是本题的最优空间方案。仓库源码佐证仓库中大量语言实现都采用了双指针写法并展示了两种不同的跳过组织方式先跳过再比较cpp/0125-valid-palindrome.cpp 与讲义结构一致用两个内层while分别让i、j越过非字母数字字符后再做tolower比较c/0125-valid-palindrome.c、dart/0125-valid-palindrome.dart 也是同款写法跳过与比较合一skip-continuego/0125-valid-palindrome.go、java/0125-valid-palindrome.java、csharp/0125-valid-palindrome.cs 采用if (!isLetterOrDigit) { i; continue; }的写法——左指针非法就前移并跳过本轮右指针同理两指针都合法时再比较语义更直白多版本并存javascript/0125-valid-palindrome.js 同时给出了正则过滤版、双指针正则版与无正则、无拷贝的纯字符比较版三种实现ruby/0125-valid-palindrome.rb 也提供反转比较与双指针两种版本可作为不同风格对比学习。此外仓库还提供 scala/0125-valid-palindrome.scala 以及 kotlin/0125-valid-palindrome.kt、swift/0125-valid-palindrome.swift 等实现基本覆盖了主流的后端与移动端语言方便对照阅读。常见陷阱Common Pitfalls陷阱一没有跳过非字母数字字符题目明确要求忽略所有非字母数字字符。如果忘记跳过空格、标点和特殊符号就会产生假阴性false negative。例如A man, a plan, a canal: Panama本应判定为回文但若把空格和标点也纳入比较结果会错误地返回false。这也是本题最容易出错的地方两个解法中都必须显式处理。陷阱二大小写敏感问题字母必须以忽略大小写的方式比较。直接拿A与a比较会得到false即使它们本应视为相等。比较前务必把两个字符统一到同一大小写统一转小写或统一转大写均可对应到各语言分别是tolower/Character.toLowerCase/char.ToLower/c.lower()/to_ascii_lowercase等 API。仓库中的 C 语言实现 c/0125-valid-palindrome.c 在比较前就明确执行了tolower(s[left])与tolower(s[right])正是对这一陷阱的防御。两种解法对比与选型建议维度反转字符串双指针核心思路清洗后与自身反转比较两端指针向内收敛、原地比较时间复杂度$O(n)$$O(n)$空间复杂度$O(n)$$O(1)$代码可读性更直观、更短稍长但逻辑清晰适用场景快速验证思路、面试开头追求最优空间、大规模输入hints/is-palindrome.md中提示的暴力解法先反转再比较对应解法一而从回文定义出发、用双指针算法高效完成对应解法二。在面试或竞赛场景中优先推荐双指针解法因为它达到了 $O(n)$ 时间、$O(1)$ 空间的最优复杂度解法一则更适合作为最直观的 baseline 帮助理解题意。总结验证回文串这道题虽然基础却浓缩了字符串类题目的三大高频考点字符过滤、大小写归一化与双指针向内收敛。本文从 articles/is-palindrome.md 的完整讲义出发覆盖了反转字符串与双指针两种解法的全部多语言实现与复杂度分析并借助仓库内 12 种语言的源码实现python/0125-valid-palindrome.py、go/0125-valid-palindrome.go、javascript/0125-valid-palindrome.js 等交叉印证了各语言的写法差异。掌握本题后可以继续挑战仓库中的 articles/valid-palindrome-ii.md允许删除一个字符再判断回文以及 articles/palindrome-linked-list.md链表回文判断将双指针技巧迁移到更复杂的场景中。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考