Skip to content

LeetCode 125 - Valid Palindrome

Difficulty: easy

Table of Contents

Open Table of Contents


Determine if a given string s is a palindrome, considering only alphanumeric characters and ignoring cases. A palindrome is a word that reads the same backward as forward.

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.



Using Two Pointers:

Solution: Two Pointers

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left, right = 0, len(s) - 1

        while left < right:
            # Move left pointer to the next alphanumeric character
            while left < right and not s[left].isalnum():
                left += 1
            # Move right pointer to the previous alphanumeric character
            while right > left and not s[right].isalnum():
                right -= 1

            if s[left].lower() != s[right].lower():
                return False

            left += 1
            right -= 1

        return True

Time and Memory Complexity

Visual Representation

Initial String:

"A man, a plan, a canal: Panama"

Pointer Movement and Comparison:

  1. Result:
    • If all corresponding characters matched, return true.
    • If any mismatch is found during the comparisons, return false.

In our example, all the comparisons will be true, and the pointers will eventually cross each other without finding any mismatch, confirming that the string is a palindrome after considering only the alphanumeric characters and ignoring the cases.

Here’s a step-by-step visual representation of the pointer movement:

"A man, a plan, a canal: Panama"
 ^                            ^
left                         right

"A  man, a plan, a canal: Panama"
   ^                          ^
  left                       right

"A  man, a plan, a canal: Panama"
    ^                         ^
   left                     right


"A man, a plan, a canal: Panama"
                ^  ^
            left   right