1. Valid Palindrome (LeetCode)
Model answer
The task
Determine whether a string reads the same forward and backward after disregarding characters that are not letters or digits and treating uppercase and lowercase as equivalent.
Key idea
Compare characters from both ends, skipping anything that should be ignored. If every remaining pair matches, the string is a palindrome.
Approach
- Initialize pointers at the start and end of the string.
- Move the left pointer past non-alphanumeric characters.
- Move the right pointer past non-alphanumeric characters.
- Compare the lowercase forms of the characters at the pointers; return
Falseif they differ. - Move both pointers inward and continue. If they meet or cross, return
True.
class Solution:
def isPalindrome(self, s: str) -> bool:
left, right = 0, len(s) - 1
while left < right:
# Ignore characters that are not letters or digits.
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
# Compare without regard to letter case.
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return True
Complexity:
- Time: O(n), where n is the string length; each pointer moves only inward.
- Space: O(1), since the comparisons use no additional data structure.
Common follow-ups
- What if the input contains no letters or digits? It is considered a palindrome, since there are no mismatching characters.
- Can you avoid creating a normalized copy of the string? Yes; the two-pointer scan uses constant extra space.
- How would you handle Unicode normalization? Normalize the string first if canonically equivalent characters should compare as equal; that may require additional space.