验证回文串 Valid Palindrome 双指针解法LeetCode 仓库多语言实现与复杂度全解析【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本文围绕经典算法题“验证回文串”Valid Palindrome展开以仓库 hints/is-palindrome.md 中的提示线索为主线系统讲解反转字符串比较与双指针原地比较两种解法并对照仓库 articles/is-palindrome.md 及 Python、Java、C、JavaScript、Go、Rust 等多语言源码给出可直接运行的实现。读完本文你将掌握如何在O(n)时间、O(1)空间内完成回文判定并理解非字母数字过滤与大小写归一化两个关键细节。1. 题目背景与前置知识题目要求给定一个字符串s判断它是否是回文串。这里的“回文”判定遵循三个规则只考虑字母和数字alphanumeric忽略空格、标点及其他特殊字符忽略大小写A与a视为相同正读与反读一致即为回文。例如A man, a plan, a canal: Panama应判定为回文而race a car不是回文。在动手写代码前需要具备三项基础能力对应 articles/is-palindrome.md 的 Prerequisites 部分双指针Two Pointers从字符串两端向中间收敛高效比较字符字符串操作String Manipulation过滤字符、大小写转换、反转字符串字符分类Character Classification判断一个字符是否为字母或数字。2. 解法一反转字符串清洗后比较2.1 思路既然只关心字母和数字可以先构造一个“清洗版”字符串newStr仅保留原串中的字母和数字并统一转为小写。此时问题退化为最简单形式——一个字符串是回文当且仅当它与其反转串完全相同。这一思路也正是 hints/is-palindrome.md 中 Hint 1 描述的暴力解法A brute force solution would be to create a copy of the string, reverse it, and then check for equality.2.2 算法步骤初始化空字符串newStr遍历输入串的每个字符c若c是字母或数字转为小写后追加到newStr比较newStr与其反转结果相等返回true否则返回false。2.3 多语言实现class Solution: def isPalindrome(self, s: str) - bool: newStr for c in s: if c.isalnum(): newStr c.lower() return newStr newStr[::-1]public 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()); } }class 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()); } };class Solution { isAlphanumeric(char) { return ( (char a char z) || (char A char Z) || (char 0 char 9) ); } isPalindrome(s) { let newStr ; for (let c of s) { if (this.isAlphanumeric(c)) { newStr c.toLowerCase(); } } return newStr newStr.split().reverse().join(); } }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()); } }func 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) }class Solution { fun isPalindrome(s: String): Boolean { var newStr for (c in s) { if (c.isLetterOrDigit()) { newStr c.lowercaseChar() } } return newStr newStr.reversed() } }class 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()) } }impl 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() } }2.4 复杂度分析时间复杂度$O(n)$——需要遍历一次字符串完成清洗再比较一次反转结果其中n为输入串长度空间复杂度$O(n)$——额外创建了清洗后的字符串与反转串。仓库中 python/0125-valid-palindrome.py 正是该思路的紧凑实现用isalpha() or isdigit()过滤字符后转小写拼接最后通过new new[::-1]完成比较rust/0125-valid-palindrome.rs 则使用chars()迭代器配合filter/map链式处理先清洗、再逐位对比。两种实现都体现了“先归一化、后判定”的同一套路。3. 解法二双指针原地比较3.1 思路反转字符串的方案虽然直观却多花了O(n)的额外空间。hints/is-palindrome.md 的 Hint 1 末尾提出了关键追问Can you think of a way to do this withoutO(n)space?答案正是双指针。回文的定义——从开头读与从结尾读完全相同对应 Hint 2 与 Hint 3 的引导——意味着开头位置的字符应当与结尾对称位置的字符相等。因此可以左指针l指向字符串开头右指针r指向结尾两个指针交替向中间移动跳过非字母数字字符每到达一对有效字符就转小写后比较一旦不相等立即判定非回文。3.2 算法步骤初始化l 0、r len(s) - 1当l r时循环将l前移直到指向字母或数字将r后移直到指向字母或数字比较s[l]与s[r]的小写形式不相等则返回falsel 1、r - 1同时向内收拢循环结束仍未发现失配返回true。3.3 多语言实现class 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))public 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); } }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 (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); } };class Solution { 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; } alphaNum(c) { return ( (c A c Z) || (c a c z) || (c 0 c 9) ); } }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); } }func 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) }class 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 } }class 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 } }impl 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 } }3.4 复杂度分析时间复杂度$O(n)$——每个字符最多被两个指针各访问一次整体线性空间复杂度$O(1)$——只使用两个指针变量不复制任何字符串。这正是 hints/is-palindrome.md 开篇推荐的复杂度目标O(n)time andO(1)space。4. 仓库源码印证双指针实现的工程化细节仓库中各语言的提交版本与上文算法一一对应且体现了一些值得学习的工程细节go/0125-valid-palindrome.go先把字符串转为[]rune再取两端字符用unicode.ToLower统一大小写并用unicode.IsLetter || unicode.IsDigit判断字母数字天然规避了 ASCII 范围的限制cpp/0125-valid-palindrome.cpp文件头注释直接点明算法要旨——2 pointers, outside in, skip non-letters compare内部用isalnum与tolower完成过滤和归一化java/0125-valid-palindrome.java采用“先取两端字符遇非字母数字则单侧移动并continue”的结构逻辑分支更清晰csharp/0125-valid-palindrome.cs把“左端非法 → 左移”“右端非法 → 右移”“都合法 → 比较”三个分支写成if / else if / else可读性极佳javascript/0125-valid-palindrome.js同一文件内给出了三种变体——正则清洗 反转、双指针 正则测试、双指针 无正则无拷贝其中第三种用字符区间判断替代正则避免了对每个字符执行正则匹配的额外开销。可以推断无论采用何种语言双指针方案的核心不变式都是指针相遇前任何一对有效字符失配即提前返回false全部通过则返回true。由于指针只在字符串上移动、不申请与n相关的容器空间复杂度才能稳定保持在O(1)。5. 常见陷阱5.1 忘记跳过非字母数字字符题目明确要求忽略所有非字母、非数字字符。若忘记跳过空格、标点和特殊符号会出现假阴性。典型例子A man, a plan, a canal: Panama若把空格与标点纳入比较正读与反读显然对不上会错误地返回false。因此过滤逻辑是正确性的第一道关口。5.2 大小写敏感比较前必须统一大小写。直接比较A与a会返回不相等但题目要求二者视为相同。无论是使用语言内建的toLowerCase()/tolower()/ToLower还是手动通过 ASCII 偏移如 Go 版本中的c a - A都必须保证两个字符在同一基准下比较。6. 从提示到实现Hint 的解题路径回顾 hints/is-palindrome.md 给出的引导链它实际构成了一条完整的思维路径复杂度目标先明确答案应达到O(n)时间、O(1)空间Hint 1暴力解法复制 → 反转 → 比较虽然时间是O(n)但空间也是O(n)引导思考能否去掉额外空间Hint 2观察定义从“正读反读相同”的定义本身寻找规律而不是依赖现成 APIHint 3双指针起点字符应与对称位置的终点字符相等从而引出双指针从两端向中间收敛的算法。这条路径的价值在于它把“会做”升级为“理解为什么这样做”。面试或工程实践中先给出反转方案证明正确性再优化为双指针方案是展示渐进式优化能力的标准范式。7. 复杂度对比与总结解法时间复杂度空间复杂度是否修改原串适用场景反转字符串比较$O(n)$$O(n)$否代码简洁、可读性优先双指针原地比较$O(n)$$O(1)$否内存敏感、追求最优回文判定是双指针思想的经典入门题。掌握本题后可以顺藤摸瓜继续挑战仓库中的同类问题palindrome-number.md 与 c/0009-palindrome-number.c数字回文不转字符串的双指针/数学解法palindrome-linked-list.md 与 python/0234-palindrome-linked-list.py链表回文快慢指针 反转后半段valid-palindrome-ii.md 与 python/0680-valid-palindrome-ii.py允许删除一个字符的回文判定双指针加“容错”分支longest-palindrome.md 与 python/0409-longest-palindrome.py由字符构成最长回文的计数问题。这些题目共享“两端向中间比较”的核心模式区别只在于数据结构的访问方式与额外的判定条件。建议对照 articles/is-palindrome.md 的完整教程逐题练习将双指针思想内化为肌肉记忆。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
