131. Palindrome Partitioning
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"]
]
class Solution {
public:
bool isPalindrome(string s)
{
int l = s.length(), left, right;
for(left = , right = l-; left < right; left++, right--)
{
if(s[left] != s[right])
return false;
}
return true;
}
void partitionHelper(vector<vector<string>> &ans, string &s, int start, vector<string> &vec)
{
int l = s.length(), i;
if(start == l)
{
ans.push_back(vec);
return;
}
for(i = start; i < l; i++)
{
string sub = s.substr(start, i-start+);
if(isPalindrome(sub))
{
vec.push_back(sub);
partitionHelper(ans, s, i+, vec);
vec.pop_back();
}
}
}
vector<vector<string>> partition(string s) {
vector<vector<string>> ans;
vector<string> vec;
partitionHelper(ans, s, , vec);
return ans;
}
};
132. Palindrome Partitioning II
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.
class Solution {
public:
int minCut(string s) {
int l = s.length(), i, j;
if(l <= )
return ;
//判断是否为回文字符串
vector<vector<bool>> isPal(l, vector<bool>(l, false));
for(i = l-; i >= ; i--) //HERE
{
isPal[i][i] = true;
for(j = i+; j < l; j++)
{
if(s[i] == s[j] && (j == i+ || isPal[i+][j-]))
isPal[i][j] = true;
}
}
vector<int> num(l);
num[] = ;
for(i = ; i < l; i++)
{
if(isPal[][i])
{
num[i] = ;
continue;
}
num[i] = i;
for(j = ; j <= i; j++)
{
if(isPal[j][i] && num[j-]+ < num[i])
num[i] = num[j-] + ;
}
}
return num[l-];
}
};
（1）
//construct the pailndrome checking matrix
// 1) matrix[i][j] = true; if (i==j) -- only one char
// 2) matrix[i][j] = true; if (i==j+1) && s[i]==s[j] -- only two chars
// 3) matrix[i][j] = matrix[i+1][j-1]; if s[i]==s[j] -- more than two chars
注意：
在构造矩阵时，要自下往上，否则一些位置会用到的值还没有填写。
（2）
/*
* Dynamic Programming
* -------------------
*
* Define res[i] = the minimum cut from 0 to i in the string.
* The result eventually is res[s.size()-1].
* We know res[0]=0. Next we are looking for the optimal solution function f.
*
* For example, let s = "leet".
*
* f(0) = 0; // minimum cut of str[0:0]="l", which is a palindrome, so not cut is needed.
* f(1) = 1; // str[0:1]="le" How to get 1?
* f(1) might be: (1) f(0)+1=1, the minimum cut before plus the current char.
* (2) 0, if str[0:1] is a palindrome (here "le" is not )
* f(2) = 1; // str[0:2] = "lee" How to get 2?
* f(2) might be: (1) f(1) + 1=2
* (2) 0, if str[0:2] is a palindrome (here "lee" is not)
* (3) f(0) + 1, if str[1:2] is a palindrome, yes!
* f(3) = 2; // str[0:3] = "leet" How to get 2?
* f(3) might be: (1) f(2) + 1=29
* (2) 0, if str[0:3] is a palindrome (here "leet" is not)
* (3) f(0) + 1, if str[1:3] is a palindrome (here "eet" is not)
* (4) f(1) + 1, if str[2:e] is a palindrome (here "et" is not)
* OK, output f(3) =2 as the result.
*
* So, the optimal function is:
*
* f(i) = min [ f(j)+1, j=0..i-1 and str[j:i] is palindrome
* 0, if str[0,i] is palindrome ]
*
* The above algorithm works well for the smaller test cases, however for the big cases, it still cannot pass.
* Why? The way we test the palindrome is time-consuming.
*
* Also using the similar DP idea, we can construct the look-up table before the main part above,
* so that the palindrome testing becomes the looking up operation. The way we construct the table is also the idea of DP.
*
* e.g. mp[i][j]=true if str[i:j] is palindrome.
* mp[i][i]=true;
* mp[i][j] = true if str[i]==str[j] and (mp[i+1][j-1]==true or j-i<2 ) j-i<2 ensures the array boundary.
*/