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

Analysis:
    1. first glance this problem requres a loop in a loop (first approach).
       Lots of time is wasted when looping a palindrome
    2. Actually this problem test dynamic programming. Since it could be decomposed to 
       smaller problems and the answer could be generated by using the results of 
       the smaller problems. (second approach)
    3. To save even more time in second approach, we could use a simple loop to handle
       special cases like the string is composed by two palindrome strings.

"""

# first approach (skipped)
# second approach
class Solution(object):
    def minCut(self, s):
        # special cases
        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

        dp=[0]*(len(s)+1)
        for i in range(1,len(dp)):
            if s[:i]!=s[0:i][::-1]: # skip palindrome part
                # dynamic programming here
                dp[i]=min(dp[j] for j in range(i) if s[j:i]==s[j:i][::-1])+1
        return dp[-1]   
