Initial Solution
class Solution:
def isPalindrome(self, s: str) -> bool:
s = s.lower()
s= s.strip() # X
s= ''.join(filter(str.isalnum, s))
i = 0
q = len(s) - 1
for _ in range(len(s)):
if i > q:
return True
if s[i] != s[q]:
return False
i += 1
q -= 1
return True
Python
복사
Time complexity and Space Complexity
Time Complexity: O(n), where n is the length of the string. We iterate through the string once to filter and process it, then iterate through at most n/2 characters to check if it's a palindrome.
Space Complexity: O(n), where n is the length of the string. We create a new string that stores only the alphanumeric characters in lowercase.
What I didn’t know
•
how to address string
s = ''.join(filter(s.isalnum, s))
Python
복사
Other Better Solutions
Two-pointer approach with constant space - Instead of creating a filtered string, we can use two pointers to traverse from both ends of the original string, skipping non-alphanumeric characters and comparing characters directly.
class Solution:
def isPalindrome(self, s: str) -> bool:
left, right = 0, len(s) - 1
while left < right:
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return True
Python
복사
Time complexity and Space Complexity
Time Complexity: O(n), where n is the length of the string. We traverse the string once with two pointers, but each pointer moves at most n times in total.
Space Complexity: O(1), constant space. We only use two pointer variables and don't create any additional data structures that scale with input size.