Valid Palindrome

Problem

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.

Constraints:

  • 1 <= s.length <= 2 * 10^5
  • s consists only of printable ASCII characters.

Solution

This is a classic problem that uses a stack as the solution. Who hasn’t written such an algorithm?

O(n) time, O(n) space.

There is an O(1) space algorithm that doesn’t use a stack. You could use two pointers to check.

class Solution {
    public boolean isPalindrome(String s) {
        s = s.toLowerCase();
        var stack = new Stack<Character>();

        for (var c : s.toCharArray()) {
            var i = (int) c;
            if ((i >= 97 && i <= 122) || (i >= 48) && (i <= 57)) {
                stack.push(c);
            }
        }

        for (var c : s.toCharArray()) {
            var i = (int) c;
            if ((i >= 97 && i <= 122) || (i >= 48) && (i <= 57)) {
                var result = stack.pop();
                if (!result.equals(c)) {
                    return false;
                }
            }
        }

        return true;
    }
}

Recent posts from blogs that I like

An Introduction to Google’s Approach to AI Agent Security

via Simon Willison

Notes on Cramer's rule

Cramer's rule is a clever solution to the classical system of linear equations Ax=b: \[\begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \\ \end{bmatrix} \begin{bmatrix}x_1 \\ x_2 \\ x_3\end{bmatrix} = \begin{bmatrix}b_1 \\ b_2 \\ b_3\end{bmatrix}\] Usi...

via Eli Bendersky

Brandjes: Paintings as witnesses to fires 1640-1813

Dramatic paintings of towns and cities on fire, usually at night, were popular during the Dutch Golden Age, and known as brandjes. Examples to well into the 19th century.

via The Eclectic Light Company