Hide sidebar
leetcode/DSA courseSystem Design

Valid Palindrome

Valid Palindrome

StringTwo Pointers
EasyLeetCode #125
15 min

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

Example 1:

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

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

Processed: "amanaplanacanalpanama"

Is Palindrome? true

Output: true

Explanation: "amanaplanacanalpanama" is a palindrome.

Solution (Two Pointers)

The two-pointers technique is a very efficient way to solve this problem. We start with one pointer at the beginning of the string and another at the end. We move them towards each other, checking for alphanumeric characters and comparing them.

Algorithm Steps

  • Initialize a left pointer at the start of the string and a right pointer at the end.
  • While the left pointer is less than the right pointer:
  • Move the left pointer forward until it points to an alphanumeric character.
  • Move the right pointer backward until it points to an alphanumeric character.
  • Compare the characters at the left and right pointers (case-insensitively). If they are not the same, the string is not a palindrome.
  • If they are the same, move both pointers towards the center.
  • If the loop completes without finding any mismatches, the string is a palindrome.
A
m
a
n
,
a
p
l
a
n
,
a
c
a
n
a
l
:
P
a
n
a
m
a
Start with left pointer at 0 and right pointer at 29.
Valid Palindrome Solution

class Solution:
    def isPalindrome(self, s: str) -> bool:
        l, r = 0, len(s) - 1
        while l < r:
            while l < r and not self.alphanum(s[l]):
                l += 1
            while l < r and not self.alphanum(s[r]):
                r -= 1
            if s[l].lower() != s[r].lower():
                return False
            l += 1
            r -= 1
        return True

    def alphanum(self, c):
        return (ord('A') <= ord(c) <= ord('Z') or
                ord('a') <= ord(c) <= ord('z') or
                ord('0') <= ord(c) <= ord('9'))