Leetcode 125. Valid Palindrome

125. Valid Palindrome

 

오늘은 릿코드 125번 문제 Valid Palindrome 을 풀어보겠습니다.

---

문제설명

 

팔린드롬 이란 알파벳 소문자 대문자는 관계없이 문자열이 앞에서부터 읽은 것과 뒤에서부터 읽은 것이 같은 문자열을 말합니다.

 

아래 예시에서 볼 수 있듯이, 스페이스, 콜론, 반점 등과 같은 Non-alphanumeric 은 모두 제외하고 숫자 혹은 문자만으로 비교를 합니다.

 

 

Easy

 

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.

 

일단 이번 문제는 해당 인자로 받은 문자열을 모두 숫자와 문자만으로 이루어진 문자열로 바꾸는 작업이 필요하고, 앞에서 읽은 것과 뒤에서 읽은 것을 비교하면 될 것으로 보입니다.

 

문제풀이

코드부터 살펴보겠습니다.

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function(s) {
    if (!s.length)
        return true;
    const alphaNumeric = filterAlphaNumeric(s);
    return alphaNumeric === alphaNumeric.split('').reverse().join('');
};

const filterAlphaNumeric = (s, nonAlphaNumeric = new RegExp('[^a-z0-9]','gi')) => s
    .toLowerCase()
    .replace(nonAlphaNumeric, '')

우선 s스트링의 길이가 0일경우 바로 true를 리턴해줍니다.

 

if (!s.length) 와 if (s.length===0) 은 같은 의미 입니다. s.length가 0일 경우 자바스크립트는 0을 if 문에서 false로 보기 때문입니다.

 

길이가 있는 스트링이 들어올 경우, 우선 알파벳과 누메릭으로 이루어진 문자열로 치환해줍니다.

 

const filterAlphaNumeric = (s, nonAlphaNumeric = new RegExp('[^a-z0-9]','gi')) => s
    .toLowerCase()
    .replace(nonAlphaNumeric, '')

 

여기서 filterAlphaNumeric 함수의 도움을 받아 Regular Expression 을 이용해 대문자는 소문자로, nonAlphaNumeric의 경우 empty string으로 replace를 해주어서 스트링을 치환합니다.

 

s = "A man, a plan, a canal: Panama"

// return: "amanaplanacanalpanama"

 

치환된 문자열을 이용해 뒤에서 읽은 것과 자기 자신과 비교해서 같으면 true, 다르면 false 를 리턴합니다.

 

문자열의 순서를 비교하는 함수로는 문자열을 배열로 변경 후, 배열의 순서를 뒤집어주고, 다시 배열을 문자열로 바꾸는 방법이 좋습니다.

 

alphaNumeric === alphaNumeric.split('').reverse().join('');

 

위 코드같은 경우 유용하니 외워두면 좋을 듯 합니다. 릿코드에서 가끔 써먹을 때가 있습니다.

 

성능

성능이 아주 좋지는 않지만 통과했습니다.

 

같은 루프에서 앞부터 읽은 것과 뒤부터 읽은 것끼리 알파벳과 숫자만 남겨가며 포인터를 이동하는 방법으로도 풀 수 있을 듯 하네요. 그렇게 되면 공간복잡도가 O(n)에서 O(1)로 줄어들어 성능 향상을 기대할 수 있을 듯 합니다.

 

저는 이정도로 만족하고 또 다음문제에서 뵙도록 하겠습니다 :)

---

이것으로 릿코드 125번 문제 Valid Palindrome 을 풀이를 마치겠습니다.

 

※ 앞으로 모든 문제를 JavaScript 로 올릴 예정입니다.

 

다른 문제 풀이도 깃헙에서 확인 할 수 있습니다.