Valid Palindrome

Easy

Problem

Return true if the string reads the same forwards and backwards after lowercasing it and removing every character that is not a letter or digit.

Example 1

Input:  "A man, a plan, a canal: Panama"
Output: true

Example 2

Input:  "race a car"
Output: false

Test cases

Case 1

Input:    "A man, a plan, a canal: Panama"
Expected: true

Case 2

Input:    "race a car"
Expected: false

Case 3

Input:    " "
Expected: true

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Two pointers, skip non-alphanumerics

Time O(n)Space O(1)

Walk inward from both ends, skipping anything that is not a letter or digit, comparing case-insensitively.

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