25 Jul 2024•Python•Unknown

Palindrome Partitioning Ii

notes and solution files for palindrome partitioning ii.

this entry collects the solution files i have for palindrome partitioning ii. i may expand it with a fuller write-up later, but the implementation files are already here.

available solution files

Python palindrome-partitioning-ii/solution.py

Solution files

Python•palindrome-partitioning-ii/solution.py

class Solution:
    def minCut(self, s: str) -> int:
        n = len(s)
        is_palindrome = [[False] * n for _ in range(n)]
        dp = [class="syntax-number">0] * n

        for i in range(n):
            min_cut = i
            for j in range(i + class="syntax-number">1):
                if s[i] == s[j] and (i - j <= class="syntax-number">2 or is_palindrome[j + class="syntax-number">1][i - class="syntax-number">1]):
                    is_palindrome[j][i] = True
                    if j == class="syntax-number">0:
                        min_cut = class="syntax-number">0
                    else:
                        min_cut = min(min_cut, dp[j - class="syntax-number">1] + class="syntax-number">1)
            dp[i] = min_cut

        return dp[-class="syntax-number">1]

solution = Solution()
s = class="syntax-string">"aab"
print(class="syntax-string">"Minimum cuts needed for palindrome partitioning:", solution.minCut(s))