Leetcode 680. Valid Palindrome II with Python

본 문서는 https://www.udemy.com/course/master-the-coding-interview-big-tech-faang-interviews/ 강의를 참조하여 작성되었습니다.

문제

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

주어진 문자열 s에 대해 s가 최대 1개의 문자를 제거했을때 회문인지 여부를 리턴하시오.

예시

Input: s = "abca"
Output: true
Explanation: 중간에 있는 문자 'c'를 제거하면 회문이 된다.

제한

1 <= s.length <= 105
s 문자열은 영어 소문자로만 이루어져있다.

풀이법

A. 앞서

회문 판별

본 풀이에선 양 끝에서부터 포인터를 시작하여 포인터가 교차할때까지 비교, 다르면 False 교차할때까지 가면 True로 계산한다.

1. OWN

최대 1개의 문자를 지워도 된다는것이기에

문자열의 중간을 기준으로 하여

0개의 문자를 지웠을때

1개의 문자를 지우되 중간 기준 오른쪽에서 지울떄

1개의 문자를 지우되 중간 기준 왼쪽에서 지울때

이 세가지 경우를 따로 검사했다.

코드는 아래와 같다

class Solution:
    def validPalindrome(self, s: str) -> bool:
        i = 0
        j = len(s)-1
        while i <= j:
            if s[i] != s[j]:
                break
            i += 1
            j -= 1
        if i > j: 
            return True

        # 오른쪽에 1개 지우기
        i = 0
        j = len(s)-1
        once = False
        while i <= j:
            if s[i] != s[j] and not once:
                j -= 1
                once = True
                continue
            elif s[i] != s[j]:
                break
            i += 1
            j -= 1
        if i > j: 
            return True

        # 왼쪽에 1개 지우기
        i = 0
        j = len(s)-1
        once = False
        while i <= j:
            if s[i] != s[j] and not once:
                i += 1
                once = True
                continue
            elif s[i] != s[j]:
                break
            i += 1
            j -= 1
        if i > j: 
            return True

O(n)의 시간복잡도를 가지며 O(1)의 공간복잡도를 가진다.