Check if a phrase reads the same both ways, ignoring case and punctuation. Walk in from both ends, skip the junk, and compare letters.
▼The problem
LeetCode 125 (Easy). A phrase is a palindrome if, after converting all uppercase letters to lowercase and removing all non-alphanumeric characters, it reads the same forwards and backwards. Given a string s, return whether it is a palindrome.
Examples (LeetCode's): "A man, a plan, a canal: Panama" → true (cleaned: amanaplanacanalpanama); "race a car" → false (cleaned raceacar, reversed racaecar: the middle e and a differ).
The solution
def isPalindrome(s):
left, right = 0, len(s) - 1
while left < right:
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return TrueTranscript
Valid Palindrome. Lowercase a string and throw away everything that isn't a letter or a digit. Does what's left read the same forwards and backwards?
A man, a plan, a canal: Panama. Without the spaces and punctuation, it reads the same both ways, so it's true. But race a car breaks in the middle, where an e meets an a. False.
The easy way builds the cleaned string and compares it with its reverse. That's order n time, but the copy costs order n extra space.
Better: dig from both ends, like two miners tunneling through a mountain. Each miner skips the rocks, anything that isn't a letter or a digit, and they compare letters in lowercase. A match? Both step inward. A mismatch? Not a palindrome. If they meet in the middle, it is.
In code: a left and a right pointer. While left is below right, skip non alphanumeric characters on each side, compare the lowercase pair, return false if they differ, and move both inward. Then return true.
On Panama: A meets a, m meets m, and the miners hop over every space, comma and colon. Ten pairs later, both reach the c in canal: true. On race a car, r, a and c match, then e meets a: false.
Each character is visited once: order n time. And two pointers are all we keep: order one space.
Dig from both ends, skip the rocks, and meet in the middle. That's Valid Palindrome.