https://leetcode.com/problems/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:
void Parlindrome(vector<vector<bool> >& isPal, string& s) {
for(int i=;i<isPal.size();++i) {
for(int j=;j<=i;++j) {
isPal[i][j] = true;
}
}
for(int len=;len<=s.length();++len) {
for(int i=;i+len-<s.length();++i) {
int j=i+len-;
if(i==j || (s[i]==s[j] && isPal[i+][j-])) isPal[i][j] = true;
}
}
}
void dfs(vector<vector<string> >& res, vector<string>& load, vector<vector<bool> >& isPal, string& s, int idx) {
if(idx == s.length()) {
res.push_back(load);
return;
}
for(int nx=idx;nx<s.length();++nx) {
if(isPal[idx][nx]) {
load.push_back(s.substr(idx, nx-idx+));
dfs(res, load, isPal, s, nx+);
load.pop_back();
}
}
}
vector<vector<string>> partition(string s) {
vector<vector<bool> > isPal(s.length(), vector<bool>(s.length(), false));
vector<string> load; load.clear();
vector<vector<string> > res;
Parlindrome(isPal, s);
dfs(res, load, isPal, s, );
return res;
}
};
leetcode 131: Palindrome Partitioning
https://leetcode.com/problems/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:
void Parlindrome(vector<vector<bool> >&isPal, string& s) {
for(int i=;i<s.length();++i) isPal[i][i-] = true;
for(int len=;len<=s.length();++len) {
for(int i=;i+len-<s.length();++i) {
int j=i+len-;
if(i==j || (s[i]==s[j] && isPal[i+][j-])) isPal[i][j] = true;
}
}
}
void minCut(vector<vector<bool> >& isPal, vector<int>& cut, string& s) {
for(int i=;i<s.length();++i) {
if(isPal[][i] == true) {
cut[i] = ;
continue;
}
for(int pre=;pre<i;++pre) {
if(isPal[pre+][i]) {
cut[i] = min(cut[pre]+, cut[i]);
}
else cut[i] = min(cut[pre]+i-pre, cut[i]);
}
}
}
int minCut(string s) {
vector<int> cut(s.length(), INT_MAX);
vector<vector<bool> > isPal(s.length(), vector<bool>(s.length(), false));
Parlindrome(isPal, s);
minCut(isPal, cut, s);
return cut[s.length()-];
}
};
leetcode 132: Palindrome Partitioning II