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

Constraints:

• 1 <= s.length <= 2 * 10^5

• s consists only of printable ASCII characters.

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.

💡 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

class Solution {
    /**
     * @time  : O(n)
     * @space : O(1)
     */
     
    public boolean isPalindrome(String s) {
        /* base case */
        if(s.length() == 1) return true;
        
        int left = 0, right = s.length() - 1;
        
        while(left < right) {
            while(left < s.length() && !Character.isLetterOrDigit(s.charAt(left))) left++;
            while(right >= 0 && !Character.isLetterOrDigit(s.charAt(right))) right--;
            
            if(left > right) return true;
            if(Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) return false;
            
            left++;
            right--;
        }
        
        return true;
    }
}