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.
最少切几刀，才能让一个字符串的每个部分都是回文。
思路：
用cut[i] 存储从s[0] ~ s[i - 1] 的子字符串，最短切几刀。
为了方便令 cut[0] = -1
只有一个字符时不需要切刀 cut[1] = 0
其他情况下,依次假设从（-1 ~ i - 2）处切刀，如果 s切刀的后半部分是一个回文， cut[i] = cut[j] + 1; cut[i]取所有切法中数值最小的那个
代码如下：这是O(n3)方法，结果超时了....
class Solution {
public:
int minCut(string s) {
vector<int> cut(s.length() + , );
cut[] = -;
for(int i = ; i <= s.length(); i++)
{
int minNum = s.length();
for(int j = ; j < i; j++)
{
if(isPalindrome(s.substr(j, i - j)))
{
int num = cut[j] + ;
minNum = min(num, minNum);
}
}
cut[i] = minNum;
}
return cut[s.length()];
}
bool isPalindrome(string s)
{
int i = , j = s.length() - ;
while(i < j)
{
if(s[i] != s[j]) return false;
i++; j--;
}
return true;
}
};
各种截枝都通过不了，只好看别人的思路，原来可以在判断回文这里下工夫，我是每次都自己判断一遍是不是回文，实际上可以将之前求过的回文信息保存下来，方便后面的判断。
O(N2)解法
class Solution {
public:
int minCut(string s) {
vector<int> cut(s.length() + , );
vector<vector<bool>> isPalindrome(s.length() + , vector<bool>(s.length() + , false));
cut[] = -;
for(int i = ; i <= s.length(); i++)
{
int minNum = s.length();
for(int j = i - ; j >= ; j--)
{
if((s[j] == s[i-]) && (i - - j < || isPalindrome[j + ][i - ]))
{
isPalindrome[j][i - ] = true;
minNum = min(cut[j] + , minNum);
}
}
cut[i] = minNum;
}
return cut[s.length()];
}
};
还有更厉害的，上面的方法保存了判断回文的信息，这有一个不需要保存的，速度非常快
class Solution {
public:
int minCut(string s) {
int n = s.size();
vector<int> cut(n+, ); // number of cuts for the first k characters
for (int i = ; i <= n; i++) cut[i] = i-;
for (int i = ; i < n; i++) {
for (int j = ; i-j >= && i+j < n && s[i-j]==s[i+j] ; j++) // odd length palindrome
cut[i+j+] = min(cut[i+j+],+cut[i-j]);
for (int j = ; i-j+ >= && i+j < n && s[i-j+] == s[i+j]; j++) // even length palindrome
cut[i+j+] = min(cut[i+j+],+cut[i-j+]);
}
return cut[n];
}
};