LeetCode 125: Valid Palindrome Solution in Python – A Step-by-Step Guide

What Is LeetCode 125: Valid Palindrome?

In LeetCode 125: Valid Palindrome, you’re given a string s, and your task is to determine if it’s a palindrome, considering only alphanumeric characters (letters and numbers) and ignoring case, spaces, and punctuation. A palindrome reads the same forward and backward. For example, "A man, a plan, a canal: Panama" is a palindrome because, after ignoring non-alphanumeric characters and case, it becomes "amanaplanacanalpanama", which is symmetric.

Problem Statement

• Input: A string s.
• Output: A boolean—True if s is a palindrome, False otherwise.
• Rules:
• Ignore non-alphanumeric characters (e.g., spaces, commas, colons).
• Case-insensitive (e.g., 'A' = 'a').
• Empty string is a palindrome.

Constraints

• 1 <= s.length <= 2 * 10⁵
• s consists of printable ASCII characters.

Examples

• Input: s = "A man, a plan, a canal: Panama"
• Output: True
• Why: "amanaplanacanalpanama" is a palindrome.
• Input: s = "race a car"
• Output: False
• Why: "raceacar" ≠ "racaecar".
• Input: s = " "
• Output: True
• Why: Empty after filtering, which is palindromic.

Understanding the Problem: Checking Symmetry

To solve LeetCode 125: Valid Palindrome in Python, we need to check if the string reads the same backward and forward after stripping non-alphanumeric characters and normalizing case. A naive approach might involve cleaning the string and comparing it to its reverse, but we can optimize further. We’ll explore:

• Best Solution (Two-Pointer): O(n) time, O(1) space—checks in-place.
• Alternative Solution (Preprocessing): O(n) time, O(n) space—builds a new string.

Let’s dive into the Best Solution—the two-pointer approach—and break it down step-by-step.

Best Solution: Two-Pointer Approach with O(1) Space

Why This Is the Best Solution

The two-pointer approach is the top choice because it’s both efficient—O(n) time—and space-savvy—O(1) space. It uses two pointers to scan the string from both ends, skipping non-alphanumeric characters and comparing only the valid ones, all without creating extra strings. It’s like walking toward the center of a word, ignoring distractions, and checking for a mirror image—fast and lean!

How It Works

Here’s the strategy:

• Step 1: Set Pointers:
• left at start (0), right at end (len(s) - 1).
• Step 2: Move and Compare:
• While left < right:
• Skip non-alphanumeric characters by moving left right or right left.
• Compare characters (lowercase) at left and right.
• If mismatch, return False.
• If match, move left right, right left.
• Step 3: Result:
• If loop completes, return True.

Step-by-Step Example

Example: s = "A man, a plan, a canal: Panama"

• Initialize: left = 0, right = 30.
• left = 0 ('A'), right = 30 ('a'):
• Both alphanumeric, 'a' == 'a', left = 1, right = 29.
• left = 1 (' '), right = 29 ('m'):
• Skip ' ', left = 2.
• left = 2 ('m'), right = 29 ('m'):
• 'm' == 'm', left = 3, right = 28.
• left = 3 ('a'), right = 28 ('a'):
• 'a' == 'a', left = 4, right = 27.
• left = 4 ('n'), right = 27 ('n'):
• Skip ',', right = 26.
• 'n' == 'n', left = 5, right = 25.
• Continue: Skip spaces, punctuation; all pairs match (e.g., 'a' with 'a', 'l' with 'l').
• left = 15 ('a'), right = 15 ('a'):
• left >= right, done.
• Result: True.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass Solution:
    def isPalindrome(self, s: str) -> bool:
        # Step 1: Set pointers
        left, right = 0, len(s) - 1

        # Step 2: Move and compare
        while left < right:
            # Skip non-alphanumeric from left
            while left < right and not s[left].isalnum():
                left += 1
            # Skip non-alphanumeric from right
            while left < right and not s[right].isalnum():
                right -= 1
            # Compare characters
            if s[left].lower() != s[right].lower():
                return False
            left += 1
            right -= 1

        return True

• Line 4: Initialize pointers at ends.
• Line 7-16: Main loop:
• Line 9-10: Skip non-alphanumeric from left.
• Line 12-13: Skip from right.
• Line 15-16: Compare lowercase chars, return False if mismatch.
• Line 17-18: Move pointers inward.
• Line 20: Return True if all match.
• Time Complexity: O(n)—each character visited at most once.
• Space Complexity: O(1)—no extra space.

This is a symmetry-checking ninja!

Alternative Solution: String Preprocessing with Reversal

Why an Alternative Approach?

The preprocessing approach offers a straightforward alternative—O(n) time, O(n) space—by cleaning the string first and then checking if it equals its reverse. It’s like polishing the string to its essentials before mirroring it—simple and clear, though it uses more space.

How It Works

Here’s the plan:

• Step 1: Clean the String:
• Filter to keep only alphanumeric characters, convert to lowercase.
• Step 2: Reverse and Compare:
• Compare the cleaned string with its reverse.
• Step 3: Result:
• Return True if they match, False otherwise.

Step-by-Step Example

Example: s = "A man, a plan, a canal: Panama"

• Step 1: Clean:
• Filter: "AmanaplanacanalPanama".
• Lowercase: "amanaplanacanalpanama".
• Step 2: Reverse:
• Reverse: "amanaplanacanalpanama".
• Compare: "amanaplanacanalpanama" == "amanaplanacanalpanama".
• Result: True.

Code for Preprocessing Approach

Copy codeclass Solution:
    def isPalindrome(self, s: str) -> bool:
        # Step 1: Clean the string
        cleaned = ''.join(c.lower() for c in s if c.isalnum())

        # Step 2: Compare with reverse
        return cleaned == cleaned[::-1]

• Line 4: Filter and lowercase in one go.
• Line 7: Compare with reversed string.
• Time Complexity: O(n)—cleaning and reversing are linear.
• Space Complexity: O(n)—new string created.

It’s a clean-and-compare classic!

Comparing the Two Solutions

• Two-Pointer (Best):
• Pros: O(n) time, O(1) space, in-place efficiency.
• Cons: Slightly more complex logic.
• Preprocessing (Alternative):
• Pros: O(n) time, O(n) space, simple and readable.
• Cons: Extra space for new string.

Two-pointer wins for space efficiency.

Additional Examples and Edge Cases

• "0P": False ("0p" ≠ "p0").
• "ab2a": True ("ab2a" = "a2ba").
• "": True (empty is palindromic).

Both handle these seamlessly.

Complexity Breakdown

• Two-Pointer: Time O(n), Space O(1).
• Preprocessing: Time O(n), Space O(n).

Two-pointer’s leaner space shines.

Key Takeaways

• Two-Pointer: Scan and skip smartly!
• Preprocessing: Clean and reverse!
• Palindrome: Symmetry is key.
• Python Tip: isalnum() rocks—see [Python Basics](/python/basics).

Final Thoughts: Spot the Mirror

LeetCode 125: Valid Palindrome in Python is a string-checking delight. The two-pointer approach nails it with minimal space, while preprocessing offers a clear alternative. Want more string fun? Try LeetCode 5: Longest Palindromic Substring or LeetCode 680: Valid Palindrome II. Ready to check? Head to Solve LeetCode 125 on LeetCode and find that palindrome today!