Leetcode – Valid Palindrome in Python

Spread the love

Introduction

The Valid Palindrome problem is a common problem and is often used in coding interviews. It is a great way to test one’s ability to manipulate strings and understand the characteristics of palindromes. In this article, we will dissect the problem, explore various approaches to solve it, and analyze the performance of these solutions.

Understanding the Problem

In the Valid Palindrome problem on LeetCode, you are given a string and you need to determine if it is a palindrome considering only alphanumeric characters and ignoring cases.

A palindrome is a string that reads the same forwards and backward. For example, the string “A man, a plan, a canal: Panama” is considered to be a palindrome.

Constraints:

  1. The input string only consists of printable ASCII characters.
  2. The input string length doesn’t exceed 2^5 * 10^4.

Approach 1: Using Two Pointers

One common approach to solving this problem is using two pointers, one starting at the beginning of the string and the other at the end. Move the pointers towards each other, and at each step, compare the characters at the two pointers.

def is_palindrome(s):
    left, right = 0, len(s) - 1

    while left < right:
        # Move the left pointer if the character is not alphanumeric
        while left < right and not s[left].isalnum():
            left += 1

        # Move the right pointer if the character is not alphanumeric
        while left < right and not s[right].isalnum():
            right -= 1

        # Compare characters ignoring case
        if s[left].lower() != s[right].lower():
            return False
        
        # Move pointers towards each other
        left += 1
        right -= 1
    
    return True

Time Complexity:

This approach has a time complexity of O(N) where N is the length of the string, as it scans through the string once.

Approach 2: Preprocessing and then Using Two Pointers

Another approach is to first preprocess the string to remove all the non-alphanumeric characters and convert it to lower case. Once we have this cleaned-up version of the string, we can apply the two-pointer approach to check if it’s a palindrome.

def is_palindrome(s):
    # Preprocess the string
    clean_string = ''.join(c.lower() for c in s if c.isalnum())

    # Check if it's a palindrome
    return clean_string == clean_string[::-1]

Time Complexity:

The preprocessing step takes O(N) time, and comparing the string with its reverse also takes O(N) time. So, the overall time complexity is O(N).

Approach 3: Using Regular Expressions for Preprocessing

You can also use regular expressions to clean the string in the preprocessing step. This can sometimes be faster than using a loop, especially for very large strings.

import re

def is_palindrome(s):
    # Preprocess the string using regular expressions
    clean_string = re.sub('[\W_]+', '', s.lower())

    # Check if it's a palindrome
    return clean_string == clean_string[::-1]

Time Complexity:

The time complexity of this approach is also O(N), but the constant factors might be different depending on the implementation of regular expressions.

Key Insights and Tips:

  1. When working with strings, it is often useful to preprocess the string into a more convenient form.
  2. The two-pointer approach is a powerful technique for solving problems that involve strings or arrays, especially when the solution involves elements that are symmetric relative to the center.
  3. Regular expressions are a powerful tool for string manipulation but can be slower than manual string manipulation for small input sizes.

Conclusion

The Valid Palindrome problem serves as an excellent introduction to string manipulation and the two-pointer technique. Through this article, we discussed multiple approaches to solving the problem, which included preprocessing the string and employing the two-pointer technique. Understanding these fundamental concepts and techniques is crucial for tackling more complex string manipulation problems.

Leave a Reply