企业官网建设流程全解析

验证回文串 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，判断它是否是回文串。这里的“回文”判定遵循三个规则：

1. 只考虑字母和数字（alphanumeric），忽略空格、标点及其他特殊字符；
2. 忽略大小写，A与a视为相同；
3. 正读与反读一致即为回文。

例如"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 算法步骤

1. 初始化空字符串newStr；
2. 遍历输入串的每个字符c：
   • 若c是字母或数字，转为小写后追加到newStr；
3. 比较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: Vec<u8> = s .bytes() .filter(|b| b.is_ascii_alphanumeric()) .map(|b| b.to_ascii_lowercase()) .collect(); new_str == new_str.iter().copied().rev().collect::<Vec<u8>>() } }

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 算法步骤

1. 初始化l = 0、r = len(s) - 1；
2. 当l < r时循环：
   • 将l前移，直到指向字母或数字；
   • 将r后移，直到指向字母或数字；
   • 比较s[l]与s[r]的小写形式：
     • 不相等则返回false；
   • l += 1、r -= 1同时向内收拢；
3. 循环结束仍未发现失配，返回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 给出的引导链，它实际构成了一条完整的思维路径：

1. 复杂度目标：先明确答案应达到O(n)时间、O(1)空间；
2. Hint 1（暴力解法）：复制 → 反转 → 比较，虽然时间是O(n)但空间也是O(n)，引导思考能否去掉额外空间；
3. Hint 2（观察定义）：从“正读反读相同”的定义本身寻找规律，而不是依赖现成 API；
4. Hint 3（双指针）：起点字符应与对称位置的终点字符相等，从而引出双指针从两端向中间收敛的算法。

这条路径的价值在于：它把“会做”升级为“理解为什么这样做”。面试或工程实践中，先给出反转方案证明正确性，再优化为双指针方案，是展示渐进式优化能力的标准范式。

7. 复杂度对比与总结

回文判定是双指针思想的经典入门题。掌握本题后，可以顺藤摸瓜继续挑战仓库中的同类问题：

• 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