Valid Palindrome - Leetcode Solution

Problem Statement:

Given a string s, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Example 1: Input: s = "A man, a plan, a canal: Panama" Output: true Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2: Input: s = "race a car" Output: false Explanation: "raceacar" is not a palindrome.

Solution:

First we need to convert the given string to lowercase and remove any characters that are not alphanumeric. We can do this using regular expressions. Then, we can check if the string is a palindrome by comparing the characters from both ends.

In order to compare characters from both ends, we can use two pointers - one at the beginning of the string and one at the end of the string. We traverse the string from both ends until the two pointers meet in the middle. At each step we compare the characters at the two pointers.

If the characters are not equal, we can return false because the string is not a palindrome. Otherwise, we continue traversing the string until the two pointers meet in the middle.

The time complexity of this solution is O(n) because we traverse the string only once.

Here is the Python code for the solution:

import re

class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = re.sub('[^0-9a-zA-Z]', '', s).lower()
        i, j = 0, len(s) - 1
        while i < j:
            if s[i] != s[j]:
                return False
            i += 1
            j -= 1
        return True

We start by importing the re module for working with regular expressions.

Then, we define a class Solution with a method isPalindrome. The method takes a string s as input and returns a boolean value indicating whether s is a palindrome.

In the method, we first use regular expressions to remove any non-alphanumeric characters from the string and convert it to lowercase.

We then define two pointers i and j pointing respectively to the beginning and the end of the string. We traverse the string from both ends until the two pointers meet in the middle.

At each step, we compare the characters at the two pointers. If they are not equal, we return False. Otherwise, we continue traversing the string until the two pointers meet in the middle.

Finally, if we have not returned False, we return True to indicate that the string is a palindrome.

1