680. Valid Palindrome II (Two Pointers, String, Greedy)

링크 - https://leetcode.com/problems/valid-palindrome-ii/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Easy

Intuition

두 개의 포인터를 사용해서 Greedy하게 풀어야 하는 문제이다.

 

만약에 주어진 String이 Palindrome하다면 우리는 그냥 캐릭터들을 비교하면서 맞음을 확인하고 True를 반환하면 된다.

하지만 만약 중간에 틀린 글자가 있다면 우리는 선택을 해야한다. left에 있는 글자를 버릴건지, right에 있는 글자를 버릴건지.

따라서 두개의 결과 중 하나라도 True가 있다면 True를 최종적으로 반환해야한다.

Code

class Solution:
    def validPalindrome(self, s: str) -> bool:
        left, right = 0, len(s) - 1

        def helper(l, r):
            while l < r:
                if s[l] != s[r]:
                    return False
                l += 1
                r -= 1
            return True

        while left < right:
            if s[left] != s[right]:
                return helper(left + 1, right) or helper(left, right - 1)
            left += 1
            right -= 1

        return True

Complexity

Time Complexity: O(N) 중간에 틀린 글자가 있어도 지우고 계속 진행을 하기 때문에 O(N/2)만큼 탐색을 하게 된다.

Space Complexity: O(1) left right두개의 상수만 저장한다.