Valid palindrome
We'll cover the following
Check whether a string reads the same both ways, ignoring punctuation and case.
Watch it run
Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.
La0
b1
c2
,3
d4
e5
f6
,7
g8
h9
i10
,11
i12
h13
g14
,15
f16
e17
d18
,19
c20
b21
Ra22
"a" matches "a". Move both inward.
1 / 14
The idea
Complexity
| Time | Space | Why |
|---|---|---|
O(n) | O(1) | Each character is looked at once from one side. |
In Python
def is_palindrome(s):
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 += 1; r -= 1
return TrueSummary: say it in the interview
- Compare the two ends and walk inward. Skip anything that is not a letter or digit. One mismatch is enough to stop.
- Time O(n), space O(1). Each character is looked at once from one side.