12. Valid Palindrome

Given a string s, decide whether it reads the same forwards and backwards once you:

keep only the alphanumeric characters (letters a-z, A-Z and digits 0-9), dropping spaces, punctuation and everything else, and
ignore letter case, so "A" and "a" count as equal.

Return true if the cleaned-up string is a palindrome, and false otherwise. A string with no alphanumeric characters at all counts as a palindrome.

Example 1

Input: s = "Never odd, or even."
Output: true

Explanation: Cleaned up, it becomes "neveroddoreven", which is the same reversed.

Example 2

Input: s = "hello, world"
Output: false

Explanation: "helloworld" reversed is "dlrowolleh".

Example 3

Input: s = ".,!"
Output: true

Explanation: No alphanumeric characters remain, and the empty string is a palindrome.

Constraints

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

💡 Hint 1

You could build a cleaned, lowercased copy and compare it with its reverse, but that uses O(n) extra space.

💡 Hint 2

Put one pointer at each end. Skip characters that are not letters or digits, then compare the two characters case-insensitively and move both pointers inward.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Use two pointers, i from the left and j from the right. Advance i past any non-alphanumeric character and retreat j likewise. Then compare the lowercased characters at i and j: a mismatch means the string is not a palindrome; otherwise move both inward. If the pointers meet without a mismatch, it is a palindrome. No cleaned copy of the string is needed.

Time O(n)Space O(1)

function isPalindrome(s) {
  const isAlnum = (c) => /[a-z0-9]/i.test(c);
  let i = 0;
  let j = s.length - 1;
  while (i < j) {
    if (!isAlnum(s[i])) { i++; continue; }
    if (!isAlnum(s[j])) { j--; continue; }
    if (s[i].toLowerCase() !== s[j].toLowerCase()) return false;
    i++;
    j--;
  }
  return true;
}

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

/**
 * @param {string} s
 * @return {boolean}
 */
function isPalindrome(s) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit