132. Palindrome Partitioning II
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.
For example, given s = "aab", return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.
Solution: DP
class Solution(object):
def minCut(self, s):
"""
:type s: str
:rtype: int
"""
size = len(s)
cut = range(-1, size)
for idx in xrange(1, size):
for low, high in (idx, idx), (idx - 1, idx):
while low >= 0 and high < size and s[low] == s[high]:
cut[high + 1] = min(cut[high + 1], cut[low] + 1)
low -= 1
high += 1
return cut[size]