[LeetCode] Valid Palindrome

공부 주제가 떠오르지 않을 때 코딩 문제를 풀어보기로 했다.

LeetCode의 Top Interview Questions 문제들로 시작해봐야겠다!

 

여러 문제 중 Strings 카테고리의 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. 문자열 소문자 변환

2. 숫자 포함

3. 공백 및 기타 문자 제거

 

나의 풀이..

var isPalindrome = function(s) {
    s = s.toLowerCase().replace(/[^a-z0-9]/g, "");

    for(let i=0; i<s.length/2; i++) {
        if(s.charAt(i) != s.charAt(s.length-i-1)) {
            return false;
        }
    }
    return true;
};

 

요건대로 문자열을 대문자에서 소문자로 변환한다.

그리고 정규식을 활용해 영문 소문자와 숫자를 제외한 문자는 제거한다.

그 이후 문자열의 중간까지만 반복문을 돌린다.

 

첫 문자와 마지막 문자를 비교하고 서로 다르면 팰린드롬이 아닌 것으로 판단한다.

비교할 때마다 첫 문자에서 다음 문자로 이동, 마지막 문자는 이전 문자로 이동하면서 중간 문자까지 검증해본다.

반복문을 무사히 마친다면 해당 문자열은 팰린드롬으로 판단한다.

 

가장 기본적인 풀이였고 Example 3를 바로 대응하기 위해 아래 코드까지 넣어주면 좀 더 빨라진다.

if(s == " ") return true;

 

다른 사람의 풀이를 봤을 때 신기했던 풀이도 있었다.

var onlyLetters = s.toLowerCase().replace(/[^a-z0-9]/g,'');
var onlyLettersReverse = onlyLetters.split("").reverse().join("");
return onlyLetters == onlyLettersReverse;

 

다양한 함수를 통해 깔끔하게 완성한 코드였다.

split으로 문자열을 쪼갠 문자 함수를 만들고 reverse를 통해 거꾸로 뒤집은 뒤 다시 문자열로 합쳐준다.

그 이후 기존 문자와 비교를 통해 팰린드롬을 판단한다.

 

속도는 위의 코드가 훨씬 빠르지만 메모리 효율은 조금 떨어지는 것을 확인했다.

다양한 코드를 경험하면서 상황에 알맞은 코드를 작성하도록 해야겠다!