Valid Palindrome

NeetCode: Valid Palindrome · LeetCode: 125. Valid Palindrome · Difficulty: Easy

A phrase is a palindrome if, after lowercasing it and removing every character that isn't a letter or digit, it reads the same forwards and backwards. Return true if the string is a palindrome.

Example

Text

Input:  s = "Was it a car or a cat I saw?"    Output: true
Input:  s = "tab a cat"                       Output: false

Brute force: clean, reverse, compare

Build a cleaned lowercase copy in a StringBuilder, reverse it with reverse(), and compare the two strings with equals. Character.isLetterOrDigit tests a character, and Character.toLowerCase lowercases it.

Java

class Solution {
    public boolean isPalindrome(String s) {
        StringBuilder cleaned = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (Character.isLetterOrDigit(c)) {
                cleaned.append(Character.toLowerCase(c));
            }
        }
        String forward = cleaned.toString();
        String reversed = cleaned.reverse().toString();
        return forward.equals(reversed);
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.isPalindrome("Was it a car or a cat I saw?"));
        System.out.println(sol.isPalindrome("tab a cat"));
    }
}

Output

true
false

Time: O(n). Space: O(n) for the two copies. reverse() changes the builder, so the forward string is taken first.

Optimal: two pointers, no copy

Put one pointer at each end. Move each inward past characters that aren't alphanumeric, then compare the two characters ignoring case. If they differ it isn't a palindrome; if the pointers cross, it is.

Java

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

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.isPalindrome("Was it a car or a cat I saw?"));
        System.out.println(sol.isPalindrome("tab a cat"));
        System.out.println(sol.isPalindrome(" "));
    }
}

Output

true
false
true

Time: O(n). Space: O(1).

An empty string gives right = -1, so the outer loop does not run and the result is true. A string with no letters or digits, such as " ", is also a palindrome: the inner loops move the pointers together until they meet, and the loop ends with true. Character.isLetterOrDigit also accepts non-ASCII letters; the problem uses ASCII input, where it matches the problem statement.