Leetcode - 유효한 Palindrome(JavaScript 포함)

오늘은 Valid Palindrome Algorithm 문제를 푸는 방법을 보여드리겠습니다.

문제는 다음과 같습니다.


간단한 예를 들어 이 문자열이 회문인지 여부를 결정해 봅시다. 회문은 앞으로 쓰는 것과 뒤로 쓰는 것이 같은 문자열입니다.

"abcdcba"

그것을 해결하는 방법에는 여러 가지가 있습니다. 먼저 가장 간단하고 간단한 방법을 살펴 보겠습니다.

입력 문자열의 반전 버전이 될 새 문자열(newString += s[i])을 만들 수 있습니다. 그런 다음 새 문자열을 입력 문자열과 비교하여 서로 같은지 확인합니다. 같으면 입력 문자열이 회문임을 의미합니다.

이 솔루션은 O(N) 공간과 O(n^2) 시간 복잡도를 제공합니다. 배열을 사용하여 O(n^2)에서 O(n)까지의 시간 복잡도를 개선할 수 있습니다.

새 문자열을 만드는 대신 모든 것을 배열에 저장할 수 있습니다. 그런 다음 마지막에 배열의 모든 요소를 ​​하나의 문자열로 결합한 다음 문자열이 회문인지 확인하기 위해 비교를 수행할 수 있습니다.

문자열을 반복하고 포인터를 사용하여 이 솔루션을 개선할 수 있습니다.

첫 번째 문자에 대한 포인터와 마지막 문자에 대한 포인터로 시작할 수 있습니다. 그런 다음 두 가지를 비교합니다. 서로 같으면 포인터가 겹칠 때까지 포인터를 다음 문자로 계속 이동합니다. 그런 다음 문자열이 실제로 회문임을 나타내는 true를 반환합니다. 서로 같지 않으면 false를 반환합니다.

var isPalindrome = function(s) {

    let leftIdx = 0;
    let rightIdx = s.length - 1;

    while(leftIdx < rightIdx){
        if (s[leftIdx] !== s[rightIdx]) return false

        rightIdx --
        leftIdx ++ 

    }
    return true
};

문자열에 공백이나 다른 기호가 있으면 어떻게 해야 합니까?

"남자, 계획, 운하: 파나마"

지정된 문자가 문자인지 숫자인지 확인하기 위해 Javascript에 내장된 메서드가 없습니다. 문자열을 전달하는 도우미 메서드를 만들 수 있습니다. 하지만 저는 다른 접근 방식을 사용할 것입니다. 문자열을 반복하기 전에 공백과 기호를 모두 제거하겠습니다. 정규식과 함께 replace() 메서드를 사용합니다. 두 개의 매개변수, 바꿀 문자열과 바꿀 문자열을 받습니다.

참고: https://regexr.com/ 는 정규 표현식을 배우고 연습하기에 좋은 리소스입니다.

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

    let leftIdx = 0;
    let rightIdx = s.length - 1;

    while(leftIdx < rightIdx){
        if (s[leftIdx] !== s[rightIdx]) return false

        rightIdx --
        leftIdx ++ 

    }
    return true
};