A phrase is a palindrome if, after converting all uppercase letters to lowercase and removing every character that is not a letter or a digit, it reads the same forwards and backwards. Given a string s, return true if it is a palindrome, otherwise false.
- 1 <= s.length <= 2 * 10^5
- s contains printable ASCII characters only
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The simple approach builds a filtered lowercase string and checks it against its reverse, which costs O(n) extra space. Instead, put one pointer at each end and move them towards each other. Whenever a pointer sits on a character that is not alphanumeric, skip it. Otherwise compare the two characters in lowercase; any mismatch means it is not a palindrome.
Algorithm
- Set
l = 0andr = len(s) - 1. - While
l < r: movelright past non-alphanumeric characters, andrleft the same way. - If
lower(s[l]) != lower(s[r]), returnfalse. - Otherwise
l++,r--and continue. Returntrueat the end.
O(n)Space: O(1)class Solution: def isPalindrome(self, s: str) -> bool: l, r = 0, len(s) - 1 while l < r: while l < r and not s[l].isalnum(): l += 1 # skip symbols while l < r and not s[r].isalnum(): r -= 1 if s[l].lower() != s[r].lower(): return False l += 1 r -= 1 return True