MiddleCodeCommonNot answered yet
Palindrome check ignoring punctuation, in O(n)
Given a string of letters and punctuation, return True if it reads the same forwards and backwards, ignoring non-letter characters and case.
Requirements:
- O(n) time, O(1) extra space (two pointers).
- Skip punctuation rather than stripping into a new string.
def is_palindrome(s):
# your code hereWrite the implementation.
Use two pointers, left at the start and right at the end. Advance each past any non-letter, then compare s[left].lower() to s[right].lower(); on mismatch return False, otherwise move both inward. Stop when they cross. This is O(n) time and O(1) space — no new filtered string. Initializing right to len(s)-1 (not -1) avoids an off-by-one.
- ✗Allocating a new filtered string, giving O(n) space instead of O(1)
- ✗Forgetting to lowercase before comparing characters
- ✗Off-by-one from initializing the right pointer to
-1instead oflen(s)-1
- →How do the two pointers skip punctuation without building a new string?
- →What edge cases (empty string, all punctuation) must the loop handle?
Contents
Task
Implement is_palindrome: check palindrome-ness ignoring punctuation and case, in O(n) time and O(1) space.
Solution
def is_palindrome(s):
left, right = 0, len(s) - 1
while left < right:
if not s[left].isalpha():
left += 1
elif not s[right].isalpha():
right -= 1
elif s[left].lower() != s[right].lower():
return False
else:
left += 1
right -= 1
return TrueKey points
- Two pointers skip non-letters in place — no new string, so O(1) space.
- Compare in lowercase to ignore case.
right = len(s) - 1(not-1) — otherwise an off-by-one breaks loop exit.
Contents
