Skip to main content

LeetCode 125 - Valid Palindrome

  • Difficulty: Easy.
  • Related Topics: Two Pointers, String.
  • Link: leetcode

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) {
  const str = s.trim(" ");
  const regex = /[a-z0-9]/;
  let i = 0;
  let j = str.length - 1;

  while (j > i) {
    const letterForward = str[i].toLowerCase();
    const letterBackward = str[j].toLowerCase();
    if (!letterForward || !letterForward.match(regex)) {
      i++;
    } else if (!letterBackward || !letterBackward.match(regex)) {
      j--;
    } else if (letterForward === letterBackward) {
      j--;
      i++;
    } else {
      return false;
    }
  }
  return true;
};

Explain:

nope.

Complexity:

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