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.

这道题基本思路是DP。设DP[i]为对于子串[0,i]范围内最少切分数,初始态DP[0] = 0(因为最初并没有切分)。



pseudo-code:

        for i in 0 to s.length - 1:

                if dp[i] > 0 and dp[i] < cutMin:

                        if s[i] to s[length - 1] is palindrome:

                                min = min ( cutMin, dp[i])

                        for j in 0 to s.length:

                                if s[i] to s[j - 1] is palindrome:

                                        dp[j] = min(dp[i] + 1, dp[j])

                                if s[j] to s[length - 1] is palindrome:

                                        min = min ( cutMin, dp[i])

需要注意两点:

1. 当切至i的时候,如果从i到末尾已经是回文, 则应与最小cut数量进行比较,如果小于则进行cut。

2. 当到达的DP[i]已经比最小cut还大时应该返回,因为之后肯定所有后续结果都比最小cut要大,因此被剪枝(否则会TLE)

 


class Solution {
public:
        bool palindrome(const string&amp; s)
        {
                int i = 0, j = s.length() - 1;
                while(i &lt; j)
                {
                        if(s[i] != s[j]) return false;
                        else ++i, --j;
                }
                return true;
        }
    
        int minCut(const string&amp; s) 
        {
                int length = s.length();
                int minCut = 0x7fffffff;
        
                if(length &gt; 1 &amp;&amp; !palindrome(s))
                {
                        vector&lt;int&gt; dp(length, 0);
                        dp[0] = 0;
            
                        for(int i = 0; i &lt; length - 1; ++i)
                        {
                                if((dp[i] &gt; 0 &amp;&amp; dp[i] &lt; minCut) || i == 0)
                                {
                                        if(palindrome(s.substr(i)))
                                                minCut = min(minCut, dp[i]);
                                        for(int j = i + 1; j &lt; length; ++j)
                                        {
                                                if(palindrome(s.substr(i, j - i))) 
                                                {
                                                        dp[j] = dp[j] == 0 ? dp[i] + 1 : min(dp[j], dp[i] + 1);
                            
                                                        if(palindrome(s.substr(j)))
                                                        minCut = min(minCut, dp[j]);
                                                }
                                        }
                                }
                        }
                }
                else minCut = 0;
        
                return minCut;
        }
};
19ms

Leave a Reply

Your email address will not be published. Required fields are marked *