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.
http://www.lintcode.com/en/problem/palindrome-partitioning/
Discussion
任意一个字符的位置都可能砍或者不砍，从第0个开始，深度优先搜索。
以“aaa“为例，依次输出：
a, a, a
a, aa
aa, a
aaa
Solution
DFS
//O(n* 2^n) rum time
// Space: O(n)
class Solution {
public:
/**
* @param s: A string
* @return: A list of lists of string
*/
vector<vector<string>> partition(string s) {
// write your code here
vector<vector<string> > result;
int n = s.length();
if(n==0) return result;
vector<string> solution;
dfs(s, result, solution, 0);
return result;
}
private:
void dfs(string s, vector<vector<string> > &result, vector<string> &solution,
int start) {
int n = s.length();
if(start ==n) {
result.push_back(solution);
return;
}
for(int i = start; i<n; i++) {
if(isPalindrome(s, start, i)) {//从start开始，后面每个字符都可能砍
solution.push_back(s.substr(start, i-start+1));
dfs(s, result, solution, i+1);
solution.pop_back();
}
}
}
bool isPalindrome(string s, int start, int end) {
while(start<=end) {
if(s[start++] != s[end--]) return false;
}
return true;
}
};
Follow up
上面的算法每次调用isPalindrome花费了大量时间，而且有重复的判断，可以用一个二维数组保存下来substring是否为palindrome。
//O(2^n) rum time
// Space: O(n^2)
class Solution {
public:
/**
* @param s: A string
* @return: A list of lists of string
*/
vector<vector<string>> partition(string s) {
// write your code here
vector<vector<string> > result;
int n = s.length();
if(n==0) return result;
vector<string> solution;
vector<vector<bool>> is_palindrome(n, vector<bool>(n, false));
for(int i=0; i<n; i++) {
is_palindrome[i][i] = true;
}
for(int i=n-1; i>=0; i--) {
for(int j=i+1; j<n; j++) {
if(s[i] == s[j] && (i+1 > j-1 || is_palindrome[i+1][j-1])) {
is_palindrome[i][j] = true;
}
}
}
dfs(s, result, solution, 0, is_palindrome);
return result;
}
private:
void dfs(string s, vector<vector<string> > &result, vector<string> &solution,
int start, vector<vector<bool>> &is_palindrome) {
int n = s.length();
if(start ==n) {
result.push_back(solution);
return;
}
for(int i = start; i<n; i++) {
if(is_palindrome[start][i]) {//从start开始，后面每个字符都可能砍
solution.push_back(s.substr(start, i-start+1));
dfs(s, result, solution, i+1, is_palindrome);
solution.pop_back();
}
}
}
};