132.py

'''
 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.
'''

classSolution(object):
defminCut(self, s):
"""
 :type s: str
 :rtype: int
 """
ifnots:
return0

P= [[Falsefor_inrange(len(s))] for_inrange(len(s))]
cuts= [0for_inrange(len(s))]

forindexinrange(len(s)):
P[index][index] =True

forlengthinrange(2, len(s)+1):
foriinrange(len(s)-length+1):
j=i+length-1

iflength==2:
P[i][j] =s[i] ==s[j]
else:
P[i][j] = (s[i] ==s[j]) andP[i+1][j-1]

forindexinrange(len(s)):
ifP[0][index]:
cuts[index] =0
else:
cuts[index] =float('inf')
forjinrange(index):
ifP[j+1][index] and (cuts[index] >1+cuts[j]):
cuts[index] =1+cuts[j]

returncuts[len(s)-1]

# Time: O(N^2)
# Space: O(N^2)