10. Is Palindrome

Problem

Given a string s, return true if it is a palindrome, otherwise return false.

A palindrome is a string that reads the same forward and backward. It is also case-insensitive and ignores all non-alphanumeric characters.

Example 1:

Input: s = "Was it a car or a cat I saw?"
 
Output: true

Copy

Explanation: After considering only alphanumerical characters we have “wasitacaroracatisaw”, which is a palindrome.

Example 2:

Input: s = "tab a cat"
 
Output: false

Copy

Explanation: “tabacat” is not a palindrome.

Constraints:

• 1 <= s.length <= 1000
• s is made up of only printable ASCII characters.

---

Solution

1. Two Pointers

Time Complexity: $O(n)$ | Space Complexity: $O(1)$

To solve this problem, we use a two-pointer approach. We compare characters from the left and right ends of the string, converting them to lowercase for consistency. If either character is not alphanumeric (i.e., not a letter or a number), we skip it. This process continues until the pointers meet or cross each other.

class Solution:
    def isPalindrome(self, s: str) -> bool:
        
        l, r = 0, len(s) - 1
        while l < r:
            if not s[l].isalnum():
                l += 1
                continue
            elif not s[r].isalnum():
                r -= 1
                continue
            elif s[l].lower() != s[r].lower():
                return False
            l += 1
            r -= 1
 
        return True
 

---

2. Reverse The String

Time Complexity: $O(n)$ | Space Complexity: $O(1)$

This version of the solution simplifies the problem by first filtering out non-alphanumeric characters and converting the remaining characters to lowercase. It then checks if the processed string is equal to its reverse.

class Solution:
    def isPalindrome(self, s: str) -> bool:
 
        s = ''.join(ch.lower() if ch.isalnum() else '' for ch in s)
 
        return s == s[::-1]
 

Alternatively, we can utilize re module in Python for regular expressions:

import re
 
class Solution:
    def isPalindrome(self, s: str) -> bool:
 
        cleaned_s = re.sub(r'[^a-zA-Z0-9]', '', s).lower()
    
        return cleaned_s == cleaned_s[::-1]