LeetCode 125: Valid Palindrome (Two Pointers + Alnum Filter)
LeetCode 125StringTwo PointersInterviewToday we solve LeetCode 125 - Valid Palindrome.
Source: https://leetcode.com/problems/valid-palindrome/
English
Problem Summary
Given a string s, determine whether it is a palindrome after converting letters to lowercase and removing all non-alphanumeric characters. Return true if it is a palindrome, otherwise false.
Key Insight
Use two pointers: one from the left and one from the right. Skip characters that are not letters/digits, compare lowercase forms of valid characters, and move inward. This avoids building an extra filtered string.
Brute Force and Limitations
A baseline approach first constructs a cleaned string containing only lowercase alphanumeric chars, then checks if it equals its reverse. This is easy but needs additional O(n) space.
Optimal Algorithm Steps
1) Initialize l = 0, r = n - 1.
2) Move l right until it points to an alphanumeric char.
3) Move r left until it points to an alphanumeric char.
4) Compare lowercase versions of s[l] and s[r]; if mismatch, return false.
5) Move both pointers inward and continue until l >= r. Return true.
Complexity Analysis
Time: O(n), each character is visited at most once by either pointer.
Space: O(1), only pointer variables are used.
Common Pitfalls
- Forgetting to normalize case before comparison.
- Treating punctuation/spaces as valid characters.
- Pointer movement mistakes causing infinite loops.
- Using locale-dependent case conversions in edge environments.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public boolean isPalindrome(String s) {
int l = 0, r = s.length() - 1;
while (l < r) {
while (l < r && !Character.isLetterOrDigit(s.charAt(l))) l++;
while (l < r && !Character.isLetterOrDigit(s.charAt(r))) r--;
char cl = Character.toLowerCase(s.charAt(l));
char cr = Character.toLowerCase(s.charAt(r));
if (cl != cr) return false;
l++;
r--;
}
return true;
}
}func isPalindrome(s string) bool {
b := []byte(s)
l, r := 0, len(b)-1
isAlnum := func(c byte) bool {
return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9')
}
toLower := func(c byte) byte {
if c >= 'A' && c <= 'Z' {
return c + ('a' - 'A')
}
return c
}
for l < r {
for l < r && !isAlnum(b[l]) {
l++
}
for l < r && !isAlnum(b[r]) {
r--
}
if toLower(b[l]) != toLower(b[r]) {
return false
}
l++
r--
}
return true
}class Solution {
public:
bool isPalindrome(string s) {
int l = 0, r = (int)s.size() - 1;
while (l < r) {
while (l < r && !isalnum((unsigned char)s[l])) l++;
while (l < r && !isalnum((unsigned char)s[r])) r--;
if (tolower((unsigned char)s[l]) != tolower((unsigned char)s[r])) {
return false;
}
l++;
r--;
}
return true;
}
};class Solution:
def isPalindrome(self, s: str) -> bool:
l, r = 0, len(s) - 1
while l < r:
while l < r and not s[l].isalnum():
l += 1
while l < r and not s[r].isalnum():
r -= 1
if s[l].lower() != s[r].lower():
return False
l += 1
r -= 1
return Truevar isPalindrome = function(s) {
let l = 0, r = s.length - 1;
const isAlnum = (ch) => /[a-z0-9]/i.test(ch);
while (l < r) {
while (l < r && !isAlnum(s[l])) l++;
while (l < r && !isAlnum(s[r])) r--;
if (s[l].toLowerCase() !== s[r].toLowerCase()) return false;
l++;
r--;
}
return true;
};中文
题目概述
给定字符串 s，忽略大小写并去掉所有非字母数字字符后，判断它是否是回文串。若是返回 true，否则返回 false。
核心思路
使用双指针：左指针从头，右指针从尾，同时向中间收缩。遇到非字母数字字符就跳过；遇到有效字符后按小写比较，不相等就直接返回 false。
暴力解法与不足
可以先把字符串清洗成“全小写 + 仅字母数字”的新字符串，再判断它是否等于反转串。实现直观，但会额外占用 O(n) 空间。
最优算法步骤
1）初始化 l = 0、r = n - 1。
2）左指针右移，直到指向字母数字字符。
3）右指针左移，直到指向字母数字字符。
4）比较 s[l] 和 s[r] 的小写形式；不相等直接返回 false。
5）两指针继续向中间移动，直到相遇或交错，最后返回 true。
复杂度分析
时间复杂度：O(n)，每个字符最多被左右指针访问一次。
空间复杂度：O(1)，只使用常数额外变量。
常见陷阱
- 比较前忘记统一大小写。
- 把空格和标点误当作参与比较的字符。
- 跳过无效字符时指针更新不正确，导致死循环。
- C/C++ 中直接把有符号 char 传给 isalnum/tolower 产生未定义行为。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public boolean isPalindrome(String s) {
int l = 0, r = s.length() - 1;
while (l < r) {
while (l < r && !Character.isLetterOrDigit(s.charAt(l))) l++;
while (l < r && !Character.isLetterOrDigit(s.charAt(r))) r--;
char cl = Character.toLowerCase(s.charAt(l));
char cr = Character.toLowerCase(s.charAt(r));
if (cl != cr) return false;
l++;
r--;
}
return true;
}
}func isPalindrome(s string) bool {
b := []byte(s)
l, r := 0, len(b)-1
isAlnum := func(c byte) bool {
return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9')
}
toLower := func(c byte) byte {
if c >= 'A' && c <= 'Z' {
return c + ('a' - 'A')
}
return c
}
for l < r {
for l < r && !isAlnum(b[l]) {
l++
}
for l < r && !isAlnum(b[r]) {
r--
}
if toLower(b[l]) != toLower(b[r]) {
return false
}
l++
r--
}
return true
}class Solution {
public:
bool isPalindrome(string s) {
int l = 0, r = (int)s.size() - 1;
while (l < r) {
while (l < r && !isalnum((unsigned char)s[l])) l++;
while (l < r && !isalnum((unsigned char)s[r])) r--;
if (tolower((unsigned char)s[l]) != tolower((unsigned char)s[r])) {
return false;
}
l++;
r--;
}
return true;
}
};class Solution:
def isPalindrome(self, s: str) -> bool:
l, r = 0, len(s) - 1
while l < r:
while l < r and not s[l].isalnum():
l += 1
while l < r and not s[r].isalnum():
r -= 1
if s[l].lower() != s[r].lower():
return False
l += 1
r -= 1
return Truevar isPalindrome = function(s) {
let l = 0, r = s.length - 1;
const isAlnum = (ch) => /[a-z0-9]/i.test(ch);
while (l < r) {
while (l < r && !isAlnum(s[l])) l++;
while (l < r && !isAlnum(s[r])) r--;
if (s[l].toLowerCase() !== s[r].toLowerCase()) return false;
l++;
r--;
}
return true;
};
Comments