leetcode 132. Palindrome Partitioning II

문제

Given a string s, 
partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.

• 주어진 문자열 s 에 대해 이를 여러 문자열로 분리한다고 가정한다.
• 모든 분리된 부분 문자열이 회문이 되게할때, 최소한으로 분리할수 있는 갯수를 구하라

예시

'aab'
>> [a] | [a] | [b] 로 나뉘어도 3개의 회문으로 구성
>> [aa] | [b] 로 나뉘어도 2개의 회문으로 구성
- 최소한으로 나누는 횟수는 1회이다.
- 정답 : 1

제한

• $1 <= s.length <= 2000$
• 문자열 s는 영어 소문자로만 구성된다.

풀이

• 특정 index로 부터 시작할때 최소한의 cut의 갯수를 구한다.

class Solution:
    def minCut(self, s: str) -> int:
        N = len(s)
        dp = [[False] * N for _ in range(N)]

		# 미리 Palindrom 여부를 계산한다.
        for i in range(N - 1, -1, -1):
            dp[i][i] = True
            for j in range(i + 1, N):
                if s[i] == s[j] and (j - i == 1 or dp[i + 1][j - 1]):
                    dp[i][j] = True

        cache = {}

		# startIndex로부터 시작한 문자열이 얼마나 적은 cut으로 회문을 만들수 있는지 구한다.
        def check(startIndex: int) -> int:
            if startIndex == N:
                return -1

            if startIndex in cache:
                return cache[startIndex]

            mincut = N

			# startIndex로부터 시작한 문자열이 회문인지 확인하고 cut의 갯수를 체크한다.
            for end in range(startIndex, N):
                if dp[startIndex][end]:
                    mincut = min(mincut, 1 + check(end + 1))

            cache[startIndex] = mincut

            return mincut

        return check(0)