palindrome.py

from functools import lru_cache

def minCut(s: str) -> int:

    def is_palindrome(start, end):

        while start < end:
            if s[start] != s[end]:
                return False
            start += 1
            end += -1

        return True
def min_cuts
    sols = dict()
    for i in range(0, len(s)):
        for j in range(i + 1):
            if not is_palindrome(j, i):
                continue
            if j - 1 < 0:
                sols[i] = 0
                continue
             sols[i] = min(sols[i], 1 + sols[j - 1]) if in in sols else 1 + sols[j - 1]


    return sols[len(s) - 1]