#125
Valid Palindrome
Easy Opposite ends
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Ignoring case and every character that isn't a letter or digit, decide whether a string reads the same both ways.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: ignoring case and symbols, does it read the same both ways?
Why this works: compare from both ends, skipping anything that isn't a letter or digit.
Example: "A man, a plan, a canal: Panama"
'a' vs 'a', 'm' vs 'm', 'a' vs 'a' …all pairs match → true
✦Hints open one at a time
Use one pointer at each end.
Skip characters that aren't letters or digits with Character.isLetterOrDigit.
↗Approach
Move the left and right pointers inward, skipping non-alphanumeric characters, and compare lowercase versions. Any mismatch means false.
</>Solution (Java)
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--;
if (Character.toLowerCase(s.charAt(l)) != Character.toLowerCase(s.charAt(r))) return false;
l++;
r--;
}
return true;
}
}!Common mistake
Building a cleaned copy of the string — fine, but it uses O(n) extra space you don't need.
Complexity
- Time: O(n).
- Space: O(1).
