Valid Palindrome
Check whether a string reads the same forwards and backwards, ignoring case and punctuation, using two pointers in O(n) time and O(1) space.
Updated Quick read: 3 min read
Approaches at a glance
| Approach | Time | Space |
|---|---|---|
| Clean, reverse and compare | O(n) | O(n) |
| Two pointers | O(n) | O(1) |
The problem
A string is a palindrome if it reads the same forwards and backwards once you ignore upper and lower case and skip every character that is not a letter or digit. Return true if the given string is a palindrome.
"A man, a plan, a canal: Panama" → true ("amanaplanacanalpanama")
"race a car" → false ("raceacar")
" " → true (nothing left to compare)Approach 1: clean, reverse and compare
Build the cleaned string, reverse it, and check that the two are equal.
JavaScript
function isPalindromeReversed(text) {
const cleaned = text.toLowerCase().replace(/[^a-z0-9]/g, "");
const reversed = [...cleaned].reverse().join("");
return cleaned === reversed;
}Python
def is_palindrome_reversed(text):
cleaned = "".join(ch.lower() for ch in text if ch.isalnum())
return cleaned == cleaned[::-1]This is short and clear. Its cost is memory: it creates a cleaned copy and a reversed copy of the input.
Time O(n). Space O(n).
Approach 2: two pointers
A palindrome's first character matches its last, its second matches its second-to-last, and so on. So compare from both ends and move inwards, with no copies at all. This is the opposite-ends form of the two pointers pattern.
JavaScript
function isLetterOrDigit(ch) {
return /[a-z0-9]/i.test(ch);
}
function isPalindrome(text) {
let left = 0;
let right = text.length - 1;
while (left < right) {
if (!isLetterOrDigit(text[left])) {
left++;
} else if (!isLetterOrDigit(text[right])) {
right--;
} else {
if (text[left].toLowerCase() !== text[right].toLowerCase()) return false;
left++;
right--;
}
}
return true;
}Python
def is_palindrome(text):
left = 0
right = len(text) - 1
while left < right:
if not text[left].isalnum():
left += 1
elif not text[right].isalnum():
right -= 1
else:
if text[left].lower() != text[right].lower():
return False
left += 1
right -= 1
return TrueEach turn of the loop does exactly one thing: skip a character on the left that does not count, skip one on the right, or compare a pair and move both pointers.
Walkthrough
"race a car":
| left | right | Characters | Action |
|---|---|---|---|
| 0 | 9 | r, r | Match, move both |
| 1 | 8 | a, a | Match, move both |
| 2 | 7 | c, c | Match, move both |
| 3 | 6 | e, space | Skip the space on the right |
| 3 | 5 | e, a | Different: return false |
Time O(n): each pointer crosses the string at most once. Space O(1): only two indexes.
Try it yourself
Copy a solution from above, add the lines below, and run it. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python.
JavaScript
console.log(isPalindrome("A man, a plan, a canal: Panama")); // true
console.log(isPalindrome("race a car")); // falsePython
print(is_palindrome("A man, a plan, a canal: Panama")) # True
print(is_palindrome("race a car")) # FalseThe comment after each line is the result you should see.
Common mistakes
- Forgetting digits. Digits count as valid characters; only spaces and punctuation are skipped.
- Looping with
left <= right. When the pointers meet on the middle character there is nothing to compare it with.left < rightis enough. - Comparing before lowercasing.
"A"and"a"must be treated as equal.
Original problem: LeetCode 125: Valid Palindrome