Valid Palindrome

easy string two pointers

Problem

Given a string s, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Two pointers walk in from both ends. They each skip over non-alphanumeric characters; whenever they land on real characters, those characters must match. If the pointers cross without a mismatch, it is a palindrome.

Inputs = "Madam, I'm Adam."

Outputtrue

Stripped + lowercased: "madamimadam".

def is_palindrome(s):
    l, r = 0, len(s) - 1
    while l < r:
        while l < r and not s[l].isalnum():
            l += 1
        while l < r and not s[r].isalnum():
            r -= 1
        if s[l].lower() != s[r].lower():
            return False
        l += 1
        r -= 1
    return True

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

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

bool isPalindrome(const string& s) {
    int l = 0, r = (int)s.size() - 1;
    while (l < r) {
        while (l < r && !isalnum((unsigned char)s[l])) l++;
        while (l < r && !isalnum((unsigned char)s[r])) r--;
        if (tolower((unsigned char)s[l]) != tolower((unsigned char)s[r]))
            return false;
        l++; r--;
    }
    return true;
}

Explanation

A palindrome reads the same forwards and backwards. So the natural check is to compare the first character with the last, the second with the second-last, and so on, working our way toward the middle.

We use two pointers: l starts at the left end and r at the right end. While they have not met, we compare the characters they point at and then move them one step closer to each other.

Two extra rules from the problem: we ignore anything that is not a letter or digit, and we ignore upper/lower case. So whenever a pointer lands on a symbol or space, we just skip it, and we compare characters in lowercase.

If we ever find a real mismatch, the answer is false right away. If the pointers cross without any mismatch, every pair matched and the answer is true.

Example: "Madam, I'm Adam." cleans up to "madamimadam", which mirrors itself perfectly, so it is a palindrome.

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