[Two Pointers] Valid Palindrome

125. Valid Palindrome

지문은 링크에서 확인해주세요.

1. 해답을 보지 않고 스스로 문제를 해결한 과정

/**
 * @param {string} s
 * @return {boolean}
 
 * Runtime	: 183 ms
 * Memory	: 51 MB
 */
var isPalindrome = function(s) {
  s = s
    .replace(/[\W_]/g, "")
    .toLowerCase();

  const len = Math.floor(s.length / 2);  

  for(let i = 0; i < len; i++) {    
    console.log(s[i], s[s.length - i - 1]);

    if(s[i] !== s[s.length - i - 1]) {
      return false;
    }
  }

  return true;
};

문자열 전처리가 필요하다고 생각하여 정규표현식을 사용하였습니다. 또한, 루프는 문자열 길이의 절반만 돌아도 된다고 생각하였습니다.

2. 여러 해답을 직접 찾아서 자신이 작성한 알고리즘에 대해서 회고한 내용

2-1. Using two pointers with no preprocessing

해답의 전문은 링크를 확인해주세요.

/*
 * Runtime	: 63 ms
 * Memory	: 45.99 MB
 */
var isPalindrome = function(s){
  let left = 0, right = s.length - 1;
  while (left < right) {
    if (!isAlphaNumeric(s[left]))
        left++;
    else if (!isAlphaNumeric(s[right]))
        right--;
    else if (s[left].toLowerCase() !== s[right].toLowerCase())
        return false;
    else {
        left++;
        right--;
    }
  }
  return true;
}

function isAlphaNumeric(char) {
  const code = char.charCodeAt(0);
  return (code >= 48 && code <= 57) || (code >= 65 && code <= 90) || (code >= 97 && code <= 122);
}

필자의 해답은 문자열 전처리에 정규표현식을 사용하여 시간 성능이 떨어집니다. 본 해답은 전처리 해야할 문자가 탐색될 시, 포인터를 옮기는 방식으로 처리하여 더 나은 시간 성능을 보여줍니다.