A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.
Given a string s, return true* if it is a palindrome, or false otherwise*.
LeetCode Solutions1 <= s.length <= 2 * 105s consists only of printable ASCII characters.We iterate through the string once to filter and lowercase it, then Python's reverse slice creates another pass, so the overall time complexity is , where n is the length of the input string.
The cleaned string and its reverse each take space proportional to the input length.
This approach first filters out all non-alphanumeric characters and converts the string to lowercase, producing a cleaned version. It then checks whether the cleaned string equals its own reverse using Python's slice notation (s[::-1]). While straightforward and readable, it requires extra space to store the cleaned string and its reverse.
Each character is visited at most once by either pointer, so the total work is , where n is the length of the input string.
No auxiliary data structures are used; the two pointer variables require only constant space.
This solution uses two pointers starting at opposite ends of the string and walks them inward. At each step, it skips non-alphanumeric characters using a custom isAlphaNum helper (checking ASCII ranges directly) and then compares the characters case-insensitively. If any mismatch is found, it returns false immediately; if the pointers meet without a mismatch, the string is a palindrome. This avoids creating any auxiliary string, achieving space.
Each character is visited at most once across all pointer movements, giving a linear scan of the input of length n.
Only two pointer variables are maintained; no extra strings or data structures are allocated.
This is the cleanest two-pointer approach: left and right start at the ends of the string, and inner while loops advance each pointer past any non-alphanumeric character using the built-in isalnum() method. The outer loop then compares the characters case-insensitively and moves both pointers inward. The use of nested while loops makes the skipping logic more explicit and avoids the continue-based control flow of Solution 2.
| Approach | Rating | Time Complexity | Space Complexity | Advantages | Disadvantages |
|---|---|---|---|---|---|
| Clean and Reverse | Simple and highly readable | Requires extra space for the cleaned string and its reverse | |||
| Two Pointers with Custom Helper | Avoids built-in methods with explicit ASCII range checks | Verbose continue-based control flow reduces readability | |||
| Two Pointers | Cleanest -space solution using built-in isalnum() | No significant disadvantage |
The optimal approach for this problem is Solution 3: Two Pointers, which achieves time complexity and space complexity. It uses nested while loops to skip non-alphanumeric characters with the built-in isalnum() method, resulting in clean, idiomatic code that avoids both auxiliary strings and verbose control flow.
class Solution: def isPalindrome(self, s: str) -> bool: # Remove non-alphanumeric characters and convert to lowercase s = "".join(c for c in s if c.isalnum()).lower()
# Check if the cleaned string is equal to its reverse return s == s[::-1]class Solution: def isPalindrome(self, s: str) -> bool: left, right = 0, len(s) - 1
# Use two pointers to compare characters from both ends while left < right: # Skip non-alphanumeric characters while left < right and not s[left].isalnum(): left += 1 while left < right and not s[right].isalnum(): right -= 1
# Compare characters in a case-insensitive manner if s[left].lower() != s[right].lower(): return False
left += 1 right -= 1
return True