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"]
] 思想： 简单的深度优先搜索。
bool isPalindrome(string& s, int l, int r) {
while(l++ < r--)
if(s[l] != s[r]) return false;
return true;
}
class Solution {
public:
void dfs(string& s, vector<string>& vec2, size_t id) {
if(id == s.size()) {
vec.push_back(vec2);
return;
}
for(int end = id; end < s.size(); ++end) {
if(isPalindrome(s, id, end)) {
vec2.push_back(s.substr(id, end-id+1));
dfs(s, vec2, end+1);
vec2.pop_back();
}
}
}
vector<vector<string> > partition(string s) {
if(s == "") return vec;
vector<string> vec2;
dfs(s, vec2, 0);
return vec;
}
private:
vector<vector<string> > vec;
};
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.
思想： 动态规划:
n = s.length();
Record[i] = 0 , ( i = n || isPalindrome(i, n-1))
min(n-1-i, Record[k]+1 ( isPalindrome(i, k) ) ) , otherwise
where i belong to interval [0, n].
class Solution {
public:
int minCut(string s) {
if(s == "" || s.size() == 1) return 0;
int n = s.size();
vector<vector<bool> > D(n, vector<bool>(n, false));
vector<int> record(n, 0);
for(int i = n-1; i >= 0; --i) {
record[i] = n-1-i;
for(int j = i; j < n; ++j) {
if(s[i] == s[j] && (j-i < 2 || D[i+1][j-1])) {
D[i][j] = true;
if(j == n-1) record[i] = 0;
else record[i] = min(record[i], record[j+1]+1);
}
}
}
return record[0];
}
};