Valid Palindrome

EasyString Two Pointers

A word-play website collects palindromic phrases from its visitors. Before judging a submission, it cleans the text in two ways:

every character that is not a letter (a-z, A-Z) or a digit (0-9) is thrown away, including spaces and punctuation,
uppercase and lowercase forms of a letter are treated as the same letter.

Given the submission s, return true if the cleaned text reads the same from left to right as from right to left, and false otherwise. A submission with nothing left after cleaning counts as a palindrome.

Example 1

Input: s = "Step on no pets!"
Output: true

Explanation: After cleaning it reads "steponnopets", which is the same in both directions.

Example 2

Input: s = "Code 42, edoc"
Output: false

Explanation: The cleaned text "code42edoc" reversed is "code24edoc": the digits come out in the wrong order.

Example 3

Input: s = "#!?"
Output: true

Explanation: Cleaning removes every character, and empty text counts as a palindrome.

Constraints

s is between 1 and 200,000 characters long.
Every character of s is printable ASCII.

💡 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