125. Valid Palindrome

Problem Statement

link: https://leetcode.com/problems/valid-palindrome/ https://leetcode.cn/problems/valid-palindrome/

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:

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

Input: s = "race a car" Output: false

Input: s = " " Output: true

Solution Approach

The solution employs a two-pointer technique, checking characters from both ends of the string, and converging towards the center.

Algorithm

1. Initialization: Initiate two pointers, l and r, pointing to the start and the end of the string respectively.
2. Pointer Movement: Move pointers l and r inward until they point to alphanumeric characters, skipping any non-alphanumeric characters.
3. Comparison: Compare the characters at l and r (after converting to lowercase). If they don’t match, return False. If they match or pointers cross each other, return True.

Implement

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

    
    

Twitter  facebook  Email