[leetcode] 125. Valid Palindrome

Valid Palindrome

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

 

Example 1:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:

Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.

Example 3:

Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.

 

Constraints:

• 1 <= s.length <= 2 * 105
• s consists only of printable ASCII characters.

 

풀이 - 1

replece 메서드를 활용하면 간단하게 풀릴거같았지만 일단 생각나는대로 brute force하게 풀어보았다.

function isPalindrome(s: string): boolean {
  if (s.trim().length === 0) {
    return true;
  }

  const alphanumericArray: string[] = ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"];

  let temp: string = "";

  for (const str of s) {
    if (alphanumericArray.includes(str.toLowerCase())) {
      temp += str.toLowerCase();
    }
  }

  const isEvenNum = temp.length % 2 === 0 ? 0 : 1;

  const start = temp.slice(0, Math.floor(temp.length / 2));
  const end = temp
    .slice(Math.floor(temp.length / 2 + isEvenNum), temp.length)
    .split("")
    .reverse()
    .join("");

  return start === end;
}

영숫자를 제외한 문자열만으로 구성된 변수를 할당해놓고, 문자열의 길이에 따라 절반으로 나누어 비교하는 방식으로 풀었다.

아무래도 includes를 사용하고 split, reverse, join을 사용하여 시간복잡도를 더 줄어볼수 있는 여지가 있는것 같다.

 

풀이 - 2

function isPalindrome(s: string): boolean {
  let temp: string = s.replace(/[^a-zA-Z0-9]/g, "").toLowerCase();

  const isEvenNum = temp.length % 2 === 0 ? 0 : 1;

  const start = temp.slice(0, Math.floor(temp.length / 2));
  const end = temp.slice(Math.floor(temp.length / 2 + isEvenNum), temp.length);

  let endIdx = end.length - 1;

  for (const str of start) {
    if (str !== end[endIdx]) {
      return false;
    }
    endIdx--;
  }

  return true;
}

문자열을 한번 순회하면서 영숫자로 변환하고 소문자로 변환해야하므로 O(n)의 횟수를 줄이고 가독성을 올리는 식으로 최적화 해보았다.