Valid Palindrome
EasyConverging pointers · skip non-alphanumerics
Check letters from both ends moving inward — if they always match, it reads the same forwards and backwards.
The idea
Compare characters from both ends moving inward. Skip anything that isn't a letter or digit, and compare case-insensitively. A mismatch means it's not a palindrome.
L
R
a
,
b
c
c
b
,
A
0
1
2
3
4
5
6
7
Step 1 of 8. Compare characters from both ends, ignoring case and punctuation. Values: a, ,, b, c, c, b, ,, A. Pointers: L at index 0, R at index 7.
1/8
Optimal
timeO(n)spaceO(1)
Skip junk, compare inward.
1// walk inward from both ends2let l = 0, r = s.length - 1;3while (l < r) {4 if (!isAlnum(s[l])) { l++; continue; }5 if (!isAlnum(s[r])) { r--; continue; }6 if (s[l].toLowerCase() !== s[r].toLowerCase())7 return false;8 l++; r--;9}10return true;Input
- array
- [a, ,, b, c, c, b, ,, A]
Memory
- L
- = 0 [a]
- R
- = 7 [A]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- s = "A man, a plan, a canal: Panama"
- Output:
- true
- Explanation:
- Ignoring punctuation and case, it mirrors.
Example 2
- Input:
- s = "race a car"
- Output:
- false
- Explanation:
- 'raceacar' is not a mirror → false.
Example 3
- Input:
- s = " "
- Output:
- true
- Explanation:
- An empty string counts as a palindrome.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.