Introduction

In this blog post, we will explore how to solve the LeetCode problem "125" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers. Given a string s, return true if it is a palindrome, or false otherwise. 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. Example 3: Input: s = " " Output: true Explanation: s is an empty string "" after removing non-alphanumeric characters. Since an empty string reads the same forward and backward, it is a palindrome. Constraints: 1 <= s.length <= 2 * 105 s consists only of printable ASCII characters.

Explanation

Here's a breakdown of the approach, followed by the Python code:

• Two-Pointer Approach: Use two pointers, one starting from the beginning and the other from the end of the processed string. Move the pointers towards the center, comparing characters at each step.
• Filtering Characters: Efficiently filter out non-alphanumeric characters and convert uppercase letters to lowercase in a single pass.

• Early Exit: If characters at the two pointers don't match, immediately return False.

• Runtime Complexity: O(n), where n is the length of the input string.

• Storage Complexity: O(1) (constant) - using only a few extra variables.

Code

    def isPalindrome(s: str) -> bool:
    """
    Given a string s, return true if it is a palindrome, or false otherwise.
    """
    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