[리트코드] 680. Valid Palindrome II - python

680. Valid Palindrome II

문제

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

최대 하나의 문자를 제거해서 팰린드롭이 될 수 있는지 확인하는 문제

제한사항

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

풀이

start와 end를 순회하다가 s[start]와 s[end]가 같지 않은 부분이 생기면 두 가지로 분기한다.

• s[start] 를 제거하는 방법
• s[end]를 제거하는 방법

최대 한번 제거하라고 했으므로, 한 번 제거 후에도 팰린드롭이 되지 않는다면 종료한다.

abca

a --- a

b----c

b제거 하는 경우

c제거 하는 경우

class Solution:
    def makePalindrome(self, s:str, start:int, end: int, changed:int):
        if changed > 1:
            return False
        
        while start < end:
            if s[start] != s[end]:
                return self.makePalindrome(s, start + 1, end, changed + 1) or self.makePalindrome(s, start, end -1, changed + 1)
            start += 1
            end -= 1
        return True
                
    def validPalindrome(self, s: str) -> bool:
        return self.makePalindrome(s, 0, len(s) - 1, 0)

최대 한 번이기 때문에 백트래킹을 사용하지 않고 더 간단하게 정리할 수도 있다.

일치하지 않은 케이스와 start를 제거한 부분과 end를 제거한 케이스로 슬라이싱 한 후 둘 중에 하나라도 팰린드롭인지 확인하면된다.

class Solution:
    def validPalindrome(self, s: str) -> bool:
        start, end = 0, len(s) - 1
        
        while start <= end:
            if s[start] != s[end]:
                case1 = s[start: end] # end 제거
                case2 = s[start + 1: end + 1]# start 제거
                
                return case1 == case1[::-1] or case2 == case2[::-1]
            start += 1
            end -= 1
        
        return True