[LeetCode] Valid Palindrom (JavaScript)

young_pallete·2021년 9월 12일

JavaScript leetcode

Algorithm

목록 보기

18/32

시작하며 🌈

최근에 마음 맞는 팀원들과 함께 알고리즘 스터디를 하고 있어요.
팀원들과 열심히 투포인터 문제를 풀었던 덕분에, 이제 슬슬 투포인터도 편해진 느낌이 들어요.

이 문제가 꽤나 유명한 문제라는데, 이번 스터디 주제 겸 한 번 풀어봤습니다. 나름 제가 내린 결론이 만족스러워서 공유해볼까 하네요. 시작합니다!

풀이과정 📃

처음 이 문제를 봤을 때, 다음과 같은 생각을 했고, 접근했습니다.

N이 100000을 넘어간다. 이건 O(NlogN)을 초과하면 안된다!

그렇다면 가장 효율적인 방법은 무엇일까? 막연히 떠오르는 건 펠린드롬은 양쪽에서 시작하니, 투포인터를 쓰면 좋을 것 같다. 이는 순환 시 최악의 경우에도 O(logN)을 충분히 만족한다.

그렇다면 삭제의 케이스에는 어떻게 할까? 이는 가장 직관적인 재귀를 사용한다.

마지막의 앞쪽과 뒷쪽을 매개변수로 하여 더욱 최적화시켜준다.

삭제 여부를 1번만 체크하기 때문에 이 방법은 유효하다.

따라서, 만약 서로 다른 부분이 존재하면, 2개의 경우를 체크해준다. 앞쪽에서 삭제하는 경우와 뒤쪽에서 삭제하는 경우다.
결과적으로 둘 중 하나라도 true가 나온다면, 결국 펠린드롬 문자열 조건을 만족한다.

이렇게 최적화를 해보니, 아무리 최악의 경우라도, O(0.5 * N)을 만족하게 됩니다! (양쪽에서 줄여주고, 매개변수로 마지막의 앞과 뒤를 캐싱했기 때문이죠!)
그렇다면, 코드로는 어떻게 구현했을지, 살펴볼까요?

코드 💻

꽤나 어썸하다고 생각하는 코드입니다!
메인함수는 validPalindrome 입니다 :)

const validPalindrome = s => isPalindrome(s);

const isPalindrome = (s, prevFront, prevRear) => {
  let front = prevFront || 0;
  let rear = prevRear || s.length - 1;

  while (rear >= front) {
    if (s[front] !== s[rear]) {
      if (prevRear) return false;
      return isPalindrome(s, front + 1, rear) 
          || isPalindrome(s, front, rear - 1)
    };
    front += 1;
    rear -= 1;
  }
  
  return true;
}