You are given a string s. Keep only its letters and digits, treat upper and lower case as the
same, and return true if what is left reads the same forwards and backwards. Otherwise return
false.
Spaces, punctuation and every other character are ignored. A string with no letters or digits at all counts as a palindrome.
Example 1
- Input
- s = "Was it a car, or a cat I saw?"
- Output
- true
wasitacaroracatisaw, which reverses to itself.Example 2
- Input
- s = "Race a car"
- Output
- false
raceacar backwards is racaecar.Example 3
- Input
- s = "0P"
- Output
- false
0p backwards is p0.Constraints
sholds 1 to 2 × 10⁵ characters.- Every character is printable ASCII: letters, digits, spaces and punctuation.
Show the pattern
Two pointers
A palindrome reads the same from both ends, so compare the two ends and move inwards: two pointers, each skipping the characters that don't count.
See two pointers in a visualiserShow the approach
Use two indices: left at the start and right at the end. If s[left] isn't a letter or
digit, step left forwards; if s[right] isn't, step right backwards. Once both point at
letters or digits, compare them in lower case: if they differ, return false; otherwise step both
inwards. When the indices meet or cross, every pair matched, so return true.
Time: O(n) · Space: O(1)