easyTwo Pointers

Valid Palindrome

Ignore punctuation, spaces, and letter case. Determine whether the remaining letters and digits read the same in both directions.

LeetCode ↗

Work through the cases

3 examples

Input notation

One line of ASCII text.

Expected result

true or false.

Case 1

Input

Never odd or even

Expected output

true

Case 2

Input

hello

Expected output

false

Case 3

Input

.,!

Expected output

true

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

Check whether the string is a palindrome after ignoring case and non-alphanumeric characters. Filtering into a new string and reversing works at n ≤ 2 × 10^5, but uses O(n) extra space. A palindrome only needs matching pairs. Two pointers walk inward: skip illegal characters, compare legal ones case-insensitively. One pass, constant space.

We use two pointers i and j to point to the two ends of the string s, and then loop through the following process until i ≥ j:

1. If s[i] is not a letter or a number, move the pointer i one step to the right and continue to the next loop. 2. If s[j] is not a letter or a number, move the pointer j one step to the left and continue to the next loop. 3. If the lowercase form of s[i] and s[j] are not equal, return false. 4. Otherwise, move the pointer i one step to the right and the pointer j one step to the left, and continue to the next loop.

At the end of the loop, return true.

The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).

class Solution {
    public boolean isPalindrome(String s) {
        int i = 0, j = s.length() - 1;
        while (i < j) {
            if (!Character.isLetterOrDigit(s.charAt(i))) {
                ++i;
            } else if (!Character.isLetterOrDigit(s.charAt(j))) {
                --j;
            } else if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j))) {
                return false;
            } else {
                ++i;
                --j;
            }
        }
        return true;
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.