680. Valid Palindrome II

💡 풀이

var validPalindrome = function (s) {
  let start = 0;
  let end = s.length - 1;

  while (start < end) {
    if (s[start] !== s[end]) {
      return isPalindrome(s, start + 1, end) || isPalindrome(s, start, end - 1);
    }
    start++;
    end--;
  }
  return true;
};

const isPalindrome = (s, start, end) => {
  while (start < end) {
    if (s[start] !== s[end]) {
      return false;
    }
    start++;
    end--;
  }
  return true;
};

📝 정리

풀이 자체는 일찍 생각했는데.. 코드로 구현할 때 시간이 오래 걸렸던 문제였다.

문제의 요구사항은 주어진 string에서 하나의 요소를 제거했을 때, 해당 string이 Palindrome이 될 수 있냐를 return 해야한다. 풀이는 다음과 같다.

• 기존의 Palindrome 비교하던 것 처럼 그대로 start, end 포인터를 사용해 비교하자.

• 그렇게 반복문에서 포인터를 움직이다, s[start] !== s[end]가 다른 순간이 올 때,

• start+1과 end가 같은지 비교하고,

• end-1과 start가 같은지 비교하자.

• 여기서 end와 start를 둘다 따로 loop을 돌려줘야 판별할 수 있다. 따라서 해당 판별 함수(isPalindrome)를 따로 빼줬다. isPalindrome 함수는 일반적인 Palindrome 판별 함수다.

• 추가적으로, 두 경우를 따로 비교하기 위해 return isPalindrome(s, start + 1, end) || isPalindrome(s, start, end - 1); 이라는 코드를 작성하였다.

수정, 지적을 환영합니다!

문제 링크

https://leetcode.com/problems/valid-palindrome-ii/

LeetCode GitHub

https://github.com/tTab1204/LeetCode