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.

Example:


Input: "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

Difficulty: interview

Starter code:

class Solution:
    def minCut(self, s: str) -> int:
        

Solutions:
class Solution:
     def minCut(self, s):
         """
         :type s: str
         :rtype: int
         """
         # acceleration
         if s == s[::-1]: return 0
         if any(s[:i] == s[:i][::-1] and s[i:] == s[i:][::-1] for i in range(1, len(s))): return 1
         # algorithm
         cut = [x for x in range(-1,len(s))]  # cut numbers in worst case (no palindrome)
         for i in range(len(s)):
             r1, r2 = 0, 0
             # use i as origin, and gradually enlarge radius if a palindrome exists
             # odd palindrome
             while r1 <= i < len(s)-r1 and s[i-r1] == s[i+r1]:
                 cut[i+r1+1], r1 = min(cut[i+r1+1], cut[i-r1]+1), r1 + 1
             # even palindrome
             while r2 <= i < len(s)-r2-1 and s[i-r2] == s[i+r2+1]:
                 cut[i+r2+2], r2 = min(cut[i+r2+2], cut[i-r2]+1), r2 + 1
         return cut[-1]

class Solution:
     def minCut(self, s):
         """
         :type s: str
         :rtype: int
         """
         if s == s[::-1]: return 0
         
         for i in range(1, len(s)):
             if s[:i] == s[:i][::-1] and s[i:] == s[i:][::-1]:
                 return 1
         
         cut = [x for x in range(-1, len(s))]
         for i in range(len(s)):
             j=0
             while i - j >= 0 and i + j < len(s) and s[i - j] == s[i + j]:
                 if cut[i + j + 1]>cut[i - j] + 1:
                     cut[i + j + 1]=cut[i - j] + 1
                 j += 1
             j=0
             while i - j >= 0 and i + j + 1 < len(s) and s[i - j] == s[i + j + 1]:
                 if cut[i + j + 2]>cut[i - j] + 1:
                     cut[i + j + 2] = cut[i - j] + 1
                 j += 1
         return cut[-1]

class Solution:
     def minCut(self, s):
         if not s: return 0
 
         # Accelerate
         if s == s[::-1]: return 0                
         length = len(s)
         for i in range(1, length):
             if s[:i] == s[:i][::-1] and s[i:] == s[i:][::-1]:
                 return 1
 
         # Algorithm
         cut = [i for i in range(-1, length)]
         for i in range(length):
             r1, r2 = 0, 0
             while i - r1 >= 0 and i + r1 < len(s) and s[i - r1] == s[i + r1]:
                 cut[i + r1 + 1] = min(cut[i + r1 + 1], cut[i - r1] + 1)
                 r1 += 1
             while i - r2 >= 0 and i + r2 + 1 < len(s) and s[i - r2] == s[i + r2 + 1]:
                 cut[i + r2 + 2] = min(cut[i + r2 + 2], cut[i - r2] + 1)
                 r2 += 1
         return cut[-1]
         
         """
         :type s: str
         :rtype: int
         """


class Solution:
     def minCut(self, s):
         if not s: return 0
         if s == s[::-1]: return 0
                 
         length = len(s)
         for i in range(1, length):
             if s[:i] == s[:i][::-1] and s[i:] == s[i:][::-1]:
                 return 1
         
         cut = [i for i in range(-1, length)]
         for i in range(length):
             r1, r2 = 0, 0
             while i - r1 >= 0 and i + r1 < len(s) and s[i - r1] == s[i + r1]:
                 cut[i + r1 + 1] = min(cut[i + r1 + 1], cut[i - r1] + 1)
                 r1 += 1
             while i - r2 >= 0 and i + r2 + 1 < len(s) and s[i - r2] == s[i + r2 + 1]:
                 cut[i + r2 + 2] = min(cut[i + r2 + 2], cut[i - r2] + 1)
                 r2 += 1
         return cut[-1]
         
         """
         :type s: str
         :rtype: int
         """


class Solution:
     def minCut(self, s):
         """
         :type s: str
         :rtype: int
         """
         if s == s[::-1]:
             return 0
         for i in range(1, len(s)):
             if s[:i] == s[:i][::-1] and s[i:] == s[i:][::-1]:
                 return 1
         
         cut = [x for x in range(-1, len(s))]
         for i in range(len(s)):
             j=0
             while i - j >= 0 and i + j < len(s) and s[i - j] == s[i + j]:
                 if cut[i + j + 1]>cut[i - j] + 1:
                     cut[i + j + 1]=cut[i - j] + 1
                 j += 1
             j=0
             while i - j >= 0 and i + j + 1 < len(s) and s[i - j] == s[i + j + 1]:
                 if cut[i + j + 2]>cut[i - j] + 1:
                     cut[i + j + 2] = cut[i - j] + 1
                 j += 1
         return cut[-1]

class Solution:
     def minCut(self, s):
         """
         :type s: str
         :rtype: int
         """
         if s == s[::-1]: return 0
         for i in range(1, len(s)):
             if s[:i] == s[:i][::-1] and s[i:] == s[i:][::-1]:
                 return 1
             
             
         n = len(s)
         is_pal = [[0] * n for _ in range(n)]
         dp = [n - 1] * n
         
         for i in range(n -1, -1, -1):
             dp[i] = n - i - 1
             for j in range(i, n):
                 if s[i] == s[j] and (j - i < 2 or is_pal[i + 1][j - 1]):
                     is_pal[i][j] = 1
                     if j == n - 1:
                         dp[i] = 0
                     elif dp[j + 1] + 1 < dp[i]:
                         dp[i] = dp[j + 1] + 1
                         
         return dp[0]


class Solution:
     def minCut(self, s):
         """
         :type s: str
         :rtype: int
         """
         if s == s[::-1]:
             return 0
         for i in range(1, len(s)):
             if s[:i] == s[:i][::-1] and s[i:] == s[i:][::-1]:
                 return 1
         
         cut = [x for x in range(-1, len(s))]
         for i in range(len(s)):
             j=0
             while i - j >= 0 and i + j < len(s) and s[i - j] == s[i + j]:
                 cut[i + j + 1] = min(cut[i + j + 1], cut[i - j] + 1)
                 j += 1
             j=0
             while i - j >= 0 and i + j + 1 < len(s) and s[i - j] == s[i + j + 1]:
                 cut[i + j + 2] = min(cut[i + j + 2], cut[i - j] + 1)
                 j += 1
         return cut[-1]

class Solution:
     def minCut(self, s):
         """
         :type s: str
         :rtype: int
         """
         if s == s[::-1]: return 0
         
         for i in range(1, len(s)):
             if s[:i] == s[:i][::-1] and s[i:] == s[i:][::-1]:
                 return 1
         
         cut = [x for x in range(-1, len(s))]
         for i in range(len(s)):
             j=0
             while i - j >= 0 and i + j < len(s) and s[i - j] == s[i + j]:
                 if cut[i + j + 1]>cut[i - j] + 1:
                     cut[i + j + 1]=cut[i - j] + 1
                 j += 1
             j=0
             while i - j >= 0 and i + j + 1 < len(s) and s[i - j] == s[i + j + 1]:
                 if cut[i + j + 2]>cut[i - j] + 1:
                     cut[i + j + 2] = cut[i - j] + 1
                 j += 1
         return cut[-1]