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"]
]
为了加速运算，可以利用动态规划，求出满足回文的子串的位置
palindrome[i][j]表示了第字符串中，s[i,i+1,……, j]是否是回文
可以有以下递推公式：
if(i==j) palindrome[i][j]=true;
if(i-j=1)palindrome[i][j]=s[i]==s[j];
if(i-j>1)palindrome[i][j]=palindrome[i+1][j-1]&&s[i]==s[j]
得到了该回文表后，我们利用回溯法得到所有的子串
class Solution {
public:
vector<vector <string> > res;
vector<vector<bool> > palindrome;
string s;
int n;
vector<vector<string>> partition(string s) {
this->s=s;
this->n=s.length();
vector<vector<bool> > palindrome(n,vector<bool>(n));
getPalindrome(palindrome);
this->palindrome=palindrome;
vector <string> tmp;
getPartition(,tmp);
return res;
}
//回溯得到子串
void getPartition(int start,vector<string> tmp)
{
if(start==n)
{
res.push_back(tmp);
return;
}
for(int i=start;i<n;i++)
{
if(palindrome[start][i])
{
tmp.push_back(s.substr(start,i-start+));
getPartition(i+,tmp);
tmp.pop_back();
}
}
}
void getPalindrome(vector<vector<bool> > &palindrome)
{
int startIndex=;
int endIndex=n-;
for(int i=n-;i>=;i--)
{
for(int j=i;j<n;j++)
{
if(i==j)
{
palindrome[i][j]=true;
}
else if(j-i==)
{
palindrome[i][j]=(s[i]==s[j]);
}
else if(j-i>)
{
palindrome[i][j]=(s[i]==s[j]&&palindrome[i+][j-]);
}
}
}
}
};