The original question can be found here.
The question is asking for a given string, determine if it’s palindromic. Only alphanumeric letters are taking into account and letters’ cases are ignored.
Reverse and Compare
The first solution we can think of is create a new string by filtering out the non-alphanumeric letters, and another new string by reversing the first newly created string, then we compare if these new 2 created strings are the same.
class Solution:
def isPalindrome(self, s: str) -> bool:
filtered_string = "".join(char.lower() for char in s if char.isalnum())
return filtered_string == filtered_string[::-1]The time complexity is O(n), space complexity is O(n) since we create a couple of new strings.
2 Pointers
From time complexity perspective, we cannot do better. However, we can improve the space complexity by using 2 pointers. We use a pointer start traversing the string from left to right, and another pointer from right to left:
class Solution:
def isPalindrome(self, s: str) -> bool:
left, right = 0, len(s) - 1
while left < right:
while left < right and not self.is_valid(s[left]):
left += 1
while left < right and not self.is_valid(s[right]):
right -= 1
if left < right:
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return True
def is_valid(self, s: str) -> bool:
return s.isalnum()Time complexity: O(n). Space complexity: O(1).