125. Valid Palindrome
## description
## 125. Valid Palindrome
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.
Example 1:
1Input: s = "A man, a plan, a canal: Panama"
2Output: true
3Explanation: "amanaplanacanalpanama" is a palindrome.Example 2:
1Input: s = "race a car"
2Output: false
3Explanation: "raceacar" is not a palindrome.Example 3:
1Input: s = " "
2Output: true
3Explanation: s is an empty string "" after removing non-alphanumeric characters.
4Since an empty string reads the same forward and backward, it is a palindrome.- –1 <= s.length <= 2 * 105
- –s consists only of printable ASCII characters.
Constraints:
## notes
### Intuition
A palindrome reads the same forwards and backwards. By comparing characters from both ends moving toward the center, we can verify this property in a single pass.
### Implementation
Use left and right pointers starting at opposite ends. Iterate while l < r, comparing characters at each position. If they don't match, return False immediately. If the loop completes, the string is a valid palindrome.
### Edge-cases
The input may contain non-alphanumeric characters and mixed case. Convert the string to lowercase first, then skip over any non-alphanumeric characters during traversal by incrementing/decrementing the pointers without comparing.
- –Time: O(n) — each character visited at most once
- –Space: O(1) — only using pointers
### Complexity
## solution
1class Solution:
2 def isPalindrome(self, s: str) -> bool:
3 l, r = 0, len(s) - 1
4 s = s.lower()
5 while l < r:
6 if not s[l].isalnum():
7 l += 1
8 continue
9 if not s[r].isalnum():
10 r -= 1
11 continue
12
13 if s[l] != s[r]:
14 return False
15
16 l += 1
17 r -= 1
18
19 return True
20
21
22
23
24if __name__ == "__main__":
25 # Include one-off tests here or debugging logic that can be run by running this file
26 # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
27 solution = Solution()
28