[Leetcode] 125. Valid Palindrome - JS

https://leetcode.com/problems/valid-palindrome/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 분석

문제분석
--------------------
palindrome은 대문자를 소문자로 변환하고, 
알파벳이 아닌 것(숫자는 제외 X)을 제거하고 앞으로 읽으나 뒤로 읽으나 똑같다.
문자열 s가 palindrome인지를 판단하여 반환하라.

제한조건
--------------------
- 1 <= s.length <= 2 * 10^5
- s는 아스키 문자로 출력가능한 요소로 구성된다.

 

2. 접근 방법

접근방법 - Two Pointer
--------------------
우선 정규표현식으로 대문자를 소문자로 변환하고, 공백과 알파벳이 아닌 것들을 제거한다.
시작 포인터와 마지막 포인터를 선언하고 각 포인터에 위치한 문자가 동일하지 않으면 Palindrome이 아니다.

 

 

3. 코드

var isPalindrome = function(s) {
    s = s.replace(/[^a-zA-Z0-9]/g, '').toLowerCase();
    let i = 0;
    let j = s.length - 1;

    while (i <= j) {
        if (s[i] !== s[j]) {
            return false
        }
        i++;
        j--;
    }
    return true
    
};

 

 

4. 복잡도 분석

- 시간복잡도: O(n)

- 공간복잡도: O(1)

 

정규표현식에서 범위의 값을 체크하고 싶으면 [] 안에 넣는다.

^ 기호는 [] 바깥에서는 뒤에 오는 표현식으로 시작하는 요소를 체크하고

[] 안에서는 not(부정)의 의미로 해석된다.