125. Valid Palindrome Easy

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 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.

Approach

Input: A string s

Output: Verify if it is a palindromic string

This is a classic opposite-direction two pointers problem.

We can define two pointers: left = 0, right = len(s) - 1, pointing to the beginning and the end of the string respectively.

Then perform the following operations:

• While left < right, filter out non-alphanumeric characters.
• When we find s[left].lower() == s[right].lower(), continue moving towards the center.
• Otherwise, return False directly.
• If the loop ends without returning, it means it is a palindrome.

Implementation

python

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

        while left < right:
            # Left pointer skips non-alphanumeric characters
            while left < right and not s[left].isalnum():
                left += 1
            
            # Right pointer skips non-alphanumeric characters
            while left < right and not s[right].isalnum():
                right -= 1

            # Check if current characters (converted to lower case) are equal
            if s[left].lower() != s[right].lower():
                return False  # Not a palindrome if they differ

            # Move both pointers to continue comparison
            left += 1
            right -= 1

        return True  # All characters matched, return True

javascript

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function(s) {
    let left = 0;
    let right = s.length - 1;

    while (left < right) {
        while (!/[a-z|A-Z|0-9]/.test(s[left]) && left < right) {
            left++;
        }

        while (!/[a-z|A-Z|0-9]/.test(s[right]) && left < right) {
            right--;
        }

        if (s[left].toLowerCase() !== s[right].toLowerCase()) {
            return false
        }

        left++;
        right--;
    }

    return true;
};

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Links

125. Valid Palindrome (English)125. 验证回文串 (Chinese)