Two methods: Both Time O(n^2)

    1. center expanding: Space O(n)
    2. two dp memo: Space O(n^2)
    1. class Solution:
    2.     def minCut(self, s: str) -> int:
    3.         if not s or len(s) == 1:
    4.             return 0
    5.         n = len(s)
    6.         dpCut = [i for i in range(n)]
    8.         for i in range(n):
    9.             j = 0
    10.             while(i - j >= 0 and i + j < n and s[i-j] == s[i+j]):
    11.                 if i - j >0:
    12.                     dpCut[i+j] = min(dpCut[i+j], dpCut[i-j-1] + 1)
    13.                 else:
    14.                     dpCut[i+j] = 0
    15.                 j += 1
    17.             j = 1
    18.             while(i - j + 1>= 0 and i + j < n and s[i-j+1] == s[i+j]):
    19.                 if i - j + 1 > 0:
    20.                     dpCut[i+j] = min(dpCut[i+j], dpCut[i-j] + 1)
    21.                 else:
    22.                     dpCut[i+j] = 0
    23.                 j += 1
    25.         return dpCut[-1]
    1. class Solution:
    2.     def minCut(self, s: str) -> int:
    3.         if not s or len(s) == 1:
    4.             return 0
    5.         n = len(s)
    6.         dpPal = [[False] * n for _ in range(n)]
    7.         dpCut = [i for i in range(n)]
    9.         for j in range(n):
    10.             for i in range(j+1):
    11.                 if s[i] == s[j] and (i + 1 > j - 1 or dpPal[i+1][j-1]):
    12.                     dpPal[i][j] = True
    13.                     if i > 0:
    14.                         dpCut[j] = min(dpCut[j], dpCut[i-1] + 1)
    15.                     else:
    16.                         dpCut[j] = 0
    17.         return dpCut[-1]