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 到 j 的字串是否为回文。
class Solution { public: /* dp[k] = min{ dp[k], dp[j - 1] + 1} if s[j...k] is palindrom, 0 <=j <= k - 1; dp[k] = dp[k - 1] + 1,otherwise. */ int minCut(string s){ vector<int> dp(s.size() + 1, 0x7f7f7f7f); /* bplin[i][i] = true, but it‘s useless for this problem. */ vector<vector<bool> > bpalin(s.size(), vector<bool>(s.size(), false)); dp[0] = -1; for(int i = 0; i < s.size(); ++i) { //we assume s[i] can‘t make palindrome with items before it. dp[i + 1] = dp[i] + 1; //check if s[i] can make palindrome with items before it. //if so, we change dp[i + 1]. for(int cur = i - 1; cur >= 0; --cur) if(s[i] == s[cur] && (i - cur <= 2 || bpalin[cur + 1][i - 1])){ dp[i + 1] = min(dp[i + 1], dp[cur] + 1); bpalin[cur][i] = true; } } return dp[s.size()]; } };