NeetCode 150: Valid Palindrome

Table of contents#

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

The Approach#

The goal is to traverse the string from both ends, skipping the invalid characters & comparing the valid characters (alphanumeric) against each other. To do this, we set up two pointers, left & right.

We then move each pointer foward, & compare them if they are both pointing to a valid character. If not, we move left fowards (increase its value) & right backwards (decrease its value).

Once these two pointers meet, all relevant characters have been compared against as we only need to compared the first valid half to the second valid half of s.

My Solution#

class Solution {
    public boolean isPalindrome(String s) {
        // Initialize the left & right pointers.
        int l = 0;
        int r = s.length() - 1;

        // First check whether they both are pointing towards a valid char. If so, compare them &
        // if they are equal move them by one index, otherwise return false. 
        // If the current char not a valid char, move that pointer by one index (skipping it).
        while (l < r) {
            boolean isLeftAlphanumeric = isAlphanumeric(s.charAt(l));
            boolean isRightAlphanumeric = isAlphanumeric(s.charAt(r));
            if ((isLeftAlphanumeric) && (isRightAlphanumeric)) {
                if ((Character.toLowerCase(s.charAt(l))) == (Character.toLowerCase(s.charAt(r)))) {
                    l++;
                    r--;
                    continue;
                } else {
                    return false;
                }

            }  else {
                if (!(isLeftAlphanumeric)) {
                    l++;
                } 
                
                if (!(isRightAlphanumeric)) {
                    r--;
                }
            }
        }
        return true;
    }

    // Returns true if ch is alphanumeric.
    private boolean isAlphanumeric(char ch) {
        return ((ch >= '0' && ch <= '9') || (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z'));
    }
}

Copy

Firstly we initialize the left & right pointers. l & r respectively.

Until both pointers cross each other, we check the character it is pointing towards. If both of them are valid, compare them & if they are not equal, return false (continue if equal).

If the character a pointer is pointing towards is not valid (i.e. not alphanumeric), “skip” it by increasing l or decreasing r.

If both pointers cross successfully, all relevant characters (first half compared to second half) have been check & it is a valid palindrome, returning true.