Участник:Plague rat/Palindrome Partitioning II

Материал из DISCOPAL
Перейти к: навигация, поиск

https://leetcode.com/problems/palindrome-partitioning-ii/

class Solution:
    def minCut(self, s: str) -> int:
        if len(s) == 0:
            return 0
 
        isPalindrome = [[False for i in range(len(s))] for j in range(len(s))]
        for i in range(len(s)):
            _left = i
            _right = i + 1
            while _left >= 0 and _right < len(s) and s[_left] == s[_right]:
                isPalindrome[_left][_right] = True
                _left -= 1
                _right += 1
            _left = i
            _right = i
            while _left >= 0 and _right < len(s) and s[_left] == s[_right]:
                isPalindrome[_left][_right] = True
                _left -= 1
                _right += 1
 
        cutCount = [10 ** 9] * (len(s) + 1)
        cutCount[0] = 0
        for j in range(len(s)):
            for i in range(j + 1):
                if isPalindrome[i][j]:
                    cutCount[j + 1] = min(cutCount[i] + 1, cutCount[j + 1])
 
        return cutCount[len(s)] - 1