0125. Valid Palindrome

Easy | Two Pointer | 36 ms (95.59%), 14.7 MB (61.30%)

❓ Problem Statement

Source: LeetCode - Valid Palindrome GitHub: Solution / Performance

Given a string s, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

✍🏻 Constraints & Example

💡 Ideas

Two pointers: One from the left (start) and the other from the right (end).

Note that when left > right inside the while loop and the algorithm has not returned the False, we could return True directly.

🤖 Python3

class Solution:
    def isPalindrome(self, s: str) -> bool:
        # (base case)
        if len(s) == 1: return True
        
        # ==================================================
        #  String + Two Pointer                            =
        # ==================================================
        # time  : O(n)
        # space : O(1)
        
        left, right = 0, len(s) - 1
         
        while left < right:
            # consider only alphanumeric characters
            while left  < len(s) and not s[left].isalnum(): left += 1
            while right >= 0     and not s[right].isalnum(): right -= 1
                
            if left > right: return True
            
            # ignoring cases
            if s[left].lower() != s[right].lower(): return False
            
            left  += 1
            right -= 1
            
        return True

🤖 Java