125. Valid Palindrome

Problem

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

Note: For the purpose of this problem, we define empty string as valid palindrome.

Example 1:

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

Example 2:

Input: "race a car"
Output: false

Solution

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function(s) {
  var i = 0;
  var j = s.length - 1;
  var m = '';
  var n = '';
  while (i < j) {
    m = s[i].toLowerCase();
    n = s[j].toLowerCase();
    if (!isLetterOrDigit(m)) i++;
    else if (!isLetterOrDigit(n)) j--;
    else if (m === n) { i++; j--; }
    else return false;
  }
  return true;
};

var isLetterOrDigit = function (c) {
  return (c >= 'a' && c <= 'z') || (c >= '0' && c <= '9');
};

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).

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

    s = s.toLowerCase().replace(/[\W_]/g, '');

    let left = 0;
    let right = s.length - 1;

    while (left < right) {
        if (s[left] !== s[right])  {
            return false
        }
        left++;
        right--;
    }

    return true;

};

Complexity:

• Time complexity : O(n).
• Space complexity : O(1). left and right pointers take the constant space.