LeetCode Valid Palindrome (JavaScript)

링크 : https://leetcode.com/problems/valid-palindrome/description/

문제 설명

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.

---

문제 풀이

문자열 비교를 쉽게 하기 위해 전부 대문자로 변경

이후 left, right 2개의 포인터를 두어 각각 왼쪽, 오른쪽에서 같은 값을 가지는지 검사

-> 중간에 실패할 경우 palindrome 문자가 아님 return false

while 문이 끝나면 palindrome 문자로 return true

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function(s) {
    s = s.toUpperCase();
    let [left, right] = [0, s.length - 1];

    while (left < right) {
        while (left < right && !(s[left] >= '0' && s[left] <= '9') && !(s[left] >= 'A' && s[left] <= 'Z')) {
            left++;
        }

        while (left < right && !(s[right] >= '0' && s[right] <= '9') && !(s[right] >= 'A' && s[right] <= 'Z')) {
            right--;
        }

        if (s[left] !== s[right]) {
            return false;
        }
        
        left++;
        right--;
    }

    return true;
};

---

결론

O(n)의 시간복잡도로 해결하기 위해 left, right 의 포인터를 적절하게 이용하면 됨.

while 문 내부에 0~9, A~Z를 탐색하기 위한 while 문을 쉽게 적용하려면 정규 표현식으로 숫자 또는 문자만 포함되게 설정하면 더 짧게 코드를 작성할 수 있음

// 0~9, A~Z만 포함하는 문자열
s.toUpperCase().replace(/[^0-9A-Z]/g, '');