Part 2 · Problems · Two pointers
Valid Palindrome
#125 · Easy · LeetCode
After lowercasing and removing non-alphanumeric characters, does the string read the same both ways?
"A man, a plan, a canal: Panama" -> true "race a car" -> false
Ask before coding
- Digits count as alphanumeric?
- Empty string is true?
Hint
One pointer at each end, skip junk, compare, move inward.
Approach
Two pointers walk inward. Skip characters that aren't letters or digits. Compare lowercase. Any mismatch means false.
Time O(n) Space O(1)
Watch it run
Solution (JavaScript, tested)
function isPalindrome(s) {
const ok = c => /[a-z0-9]/i.test(c);
let l = 0,
r = s.length - 1;
while (l < r) {
if (!ok(s[l])) {
l++;
continue;
}
if (!ok(s[r])) {
r--;
continue;
}
if (s[l].toLowerCase() !== s[r].toLowerCase()) return false;
l++;
r--;
}
return true;
}Traps
- Building a cleaned copy is fine but uses O(n) memory.
- Use l < r, not l <= r.
Say out loud: I can clean and reverse, but two pointers do it in place with no extra string.