Write a function that returns whether text reads the same forwards and backwards when you only look at letters and digits and ignore upper/lower case. Spaces, punctuation and other symbols don't count.
Letters are the English letters a–z (in either case), and digits are 0–9. Try to use O(1) extra space: no cleaned-up copy of the string.
text
1is_clean_palindrome("Was it a car, or a cat I saw?") -> True
2is_clean_palindrome("No 'x' in Nixon") -> True
3is_clean_palindrome("race a car") -> False
4is_clean_palindrome("?!") -> True
The last example has no letters or digits at all, which counts as a palindrome (an empty string reads the same both ways).
Write is_clean_palindrome(text) in Python or isCleanPalindrome(text) in JavaScript. Examples are written in Python: in JavaScript, None is null and True / False are true / false.
Runs privately in your browser. Nothing is sent to a server.Ctrl/⌘ + Enter to run · Esc then Tab to leave the editor
Write your function, then run it against 22 tests.
Breakdown
Stuck? Reveal one step at a time, and try again after each one.
The easy version
Build a cleaned, lowercase copy of the string and compare it with its reverse. It's O(n) time, but O(n) extra space. Good to mention, then improve.
Step 2
Compare from both ends
Put left at the start and right at the end. If the two characters match (ignoring case), move both inwards. If they don't, it's not a palindrome.
Step 3
Skip what doesn't count
Before comparing, move left forward past anything that isn't a letter or digit, and move right backward the same way. Make sure the skipping loops also stop when the pointers meet, or they can run past each other.
Checking "Ab,ba!"1 / 4
leftright
A
0
b
1
,
2
b
3
a
4
!
5
right is on '!', which doesn't count. Skip it.
Step 4
Stop in the middle
When left >= right, every pair has matched, so the answer is yes.
Solution
Give it a real try first: you learn far more from a wrong attempt than from reading the answer.
Use two pointers moving inwards. Skip characters that aren't letters or digits on each side, compare the lowercase versions, and return false on the first mismatch. If the pointers meet, return true.
python
1def is_clean_palindrome(text):
2 def counts(ch):
↑only letters and digits count
3 return ch.isascii() and ch.isalnum()
4
5 left, right = 0, len(text) - 1
6 while left < right:
7 while left < right and not counts(text[left]):
↑skip, but never cross over
8 left += 1
9 while left < right and not counts(text[right]):
10 right -= 1
11 if text[left].lower() != text[right].lower():
↑compare ignoring case
12 return False
13 left += 1
14 right -= 1
15 return True
↑the pointers met: it's a palindrome
javascript
1function isCleanPalindrome(text) {
2 const counts = (ch) => /[a-z0-9]/i.test(ch)
↑only letters and digits count
3 let left = 0
4 let right = text.length - 1
5 while (left < right) {
6 while (left < right && !counts(text[left])) left++
↑skip, but never cross over
7 while (left < right && !counts(text[right])) right--
8 if (text[left].toLowerCase() !== text[right].toLowerCase()) return false
↑compare ignoring case
9 left++
10 right--
11 }
12 return true
↑the pointers met: it's a palindrome
13}
Complexity
TimeO(n)SpaceO(1)
O(n) time: each pointer passes over each character at most once. O(1) extra space: just two indexes.
What we learned
Two pointers from both ends check symmetric properties without copying the data.
Inner "skip" loops must also check left < right, or they can cross over and compare the wrong characters.
Say which characters count. Here it's English letters and digits; real-world text may need more care.