Leetcode 190. Valid Palindrome II

투 포인터스 카테고리로 넘어와서 맞이한 첫 문제. 시작부터 불길하다. easy가 전혀 easy가 아닌데. 난이도 누가 설정한거지? ㅂㄷㅂㄷ

---

Given a string s, return true if the s can be palindrome after deleting at most one character from it.

Example 1:

Input: s = "aba"
Output: true

Example 2:

Input: s = "abca"
Output: true
Explanation: You could delete the character 'c'.

Example 3:

Input: s = "abc"
Output: false

Constraints:

• 1 <= s.length <= 105
• s consists of lowercase English letters.

 

---

 

◇ 해결 방법

이 문제를 해결하기 위해서는 문자열을 순회하면서 양쪽 끝에서부터 하나씩 비교해 나가며, 양쪽 끝의 문자가 일치하지 않는 경우 문자 하나를 삭제하고 팰린드롬인지 검사해야 한다. 이를 위해 다음과 같은 알고리즘을 사용할 수 있다.

1. 문자열의 양쪽 끝에서부터 하나씩 비교해 나가면서, 일치하지 않는 문자가 있는지 검사한다.
2. 일치하지 않는 문자가 발견되면, 해당 문자를 삭제한 새로운 문자열을 만들어 팰린드롬인지 검사한다.
3. 팰린드롬이면 true를 반환하고, 아니면 false를 반환한다.

function isPalindrome(s) {
  let left = 0;
  let right = s.length - 1;
  while (left < right) {
    if (s[left] !== s[right]) {
      return isPalindromeRange(s, left + 1, right) || isPalindromeRange(s, left, right - 1);
    }
    left++;
    right--;
  }
  return true;
}

function isPalindromeRange(s, left, right) {
  while (left < right) {
    if (s[left] !== s[right]) {
      return false;
    }
    left++;
    right--;
  }
  return true;
}

 

◇ 시간 복잡도

이 알고리즘의 시간 복잡도는 O(N). 이는 문자열을 한 번만 순회하기 때문이다.

 

문제출처: LeetCode - The World's Leading Online Programming Learning Platform