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.
My code:
class Solution(object):
def minCut(self, s):
"""
:type s: str
:rtype: int
"""
dp = [0]*len(s)
#bottom up
for i in range(len(s)-2,-1,-1):
dp[i] = 0 if s[i:]==s[i:][::-1] else 1 + min(dp[j] for j in range(i+1,len(s)) if s[i:j] == s[i:j][::-1])
return dp[0]Solution: https://leetcode.com/problems/palindrome-partitioning-ii/