The problem
A phrase is a palindrome if, after turning uppercase letters into lowercase and removing everything that is not a letter or a digit, it reads the same forwards and backwards.
Given a string s, return true if it is a palindrome and false otherwise.
Examples
01
- Input
s = "A man, a plan, a canal: Panama"
- Output
true
02
- Input
s = "race a car"
- Output
false
Constraints
- 1 ≤ s.length ≤ 2 × 10⁵
sconsists of printable ASCII characters.
The idea
A palindrome’s first character matches its last, its second matches its second-to-last, and so on. So put one pointer at each end and walk them toward each other.
When a pointer is on a character that is not a letter or digit, step past it. When both are on letters or digits, compare them ignoring case: any mismatch means no. If the pointers meet, every pair matched. Nothing is copied or cleaned first.
- Time
- O(n) — each character is passed once
- Space
- O(1) — two indices
Solution · every language run against every case
class Solution: def isPalindrome(self, s: str) -> bool: l, r = 0, len(s) - 1 while l < r: if not s[l].isalnum(): l += 1 elif not s[r].isalnum(): r -= 1 elif s[l].lower() != s[r].lower(): return False else: l, r = l + 1, r - 1 return True