LeetCode: Palindrome Partition
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = "aab",
Return
[
["aa","b"],
["a","a","b"]
]
地址：https://oj.leetcode.com/problems/palindrome-partitioning/
算法：可以用动态规划来解决。用一个二维数组dp来存储所有子问题的解，一维数组dp[i]用来存储0～i的字串的所有解，其中每个解用最后一个回文开始位置来标记。比如对于上面的字符串“aab”，
dp[0]={0},dp[1]={0,1},dp[2]={2}。这样，在构造解的过程中就可以采用递归的方法，对dp[n-1]中的所有值dp[n-1][j]先递归构造出字串0～dp[n-1][j]-1，然后在加上dp[n-1][j]~n-1
字串。具体代码：
class Solution {
public:
vector<vector<string> > partition(string s) {
int n = s.size();
if (n < ) return vector<vector<string> >();
vector<vector<int> > dp(n);
dp[].push_back();
for (int i = ; i < n; ++i){
if(isPalindrome(s.substr(,i+))){
dp[i].push_back();
}
dp[i].push_back(i);
for (int j = i-; j >= ; --j){
if(isPalindrome(s.substr(j+,i-j))){
dp[i].push_back(j+);
}
}
}
return constructResult(s,dp,n);
}
bool isPalindrome(const string &s){
int len = s.size();
int n = len / ;
int i = ;
while(i < n && s[i] == s[len--i]) ++i;
return i == n;
}
vector<vector<string> > constructResult(string &s, vector<vector<int> > &dp,int n){
if (n < ){
return vector<vector<string> >();
}
vector<int>::iterator it = dp[n-].begin();
vector<vector<string> > result;
for (; it != dp[n-].end(); ++it){
if (*it == ){
vector<string> temp1;
temp1.push_back(s.substr(,n));
result.push_back(temp1);
continue;
}
vector<vector<string> >temp2 = constructResult(s,dp,*it);
vector<vector<string> >::iterator str_it = temp2.begin();
for(; str_it != temp2.end(); ++str_it){
str_it->push_back(s.substr(*it,n-(*it)));
result.push_back(*str_it);
}
}
return result;
}
};
第二题：
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.
地址：https://oj.leetcode.com/problems/palindrome-partitioning-ii/
算法：同样用动态规划来解决，但这次只要用一维数组dp来储存所有子问题。其中dp[i]表示字串0～i所用的最小cut，dp[i+1]=min{dp[j-1] | 0 =< j <= i+1 且 字串j~i+1是回文}。代码：
class Solution {
public:
int minCut(string s) {
int n = s.size();
if(n < ) return ;
vector<int> dp(n);
dp[] = ;
for(int i = ; i < n; ++i){
if(isPalindrome(s.substr(,i+))){
dp[i] = ;
continue;
}
int min_value = n;
for(int j = i-; j >= ; --j){
if(dp[j]+ < min_value){
if(isPalindrome(s.substr(j+,i-j))){
min_value = dp[j] + ;
}
}
}
dp[i] = min_value;
}
return dp[n-];
}
bool isPalindrome(const string &s){
int len = s.size();
int n = len / ;
int i = ;
while(i < n && s[i] == s[len--i]) ++i;
return i == n;
}
};