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"]
]
空间换时间。
使用二维数组isPalin记录每个子串是否为回文串。
然后递归来做。可以看做深度优先搜索。
class Solution {
public:
vector<vector<bool> > isPalin; // isPalin[i][j]==true means s[i,...,j] is palindrome
void buildMap(string s)
{
int n = s.size();
isPalin.resize(n, vector<bool>(n, false));
for(int i = ; i < n; i ++)
isPalin[i][i] = true;
for(int i = n-; i >= ; i --)
{
for(int j = i+; j < n; j ++)
{
if(s[i] == s[j])
{
if(j == i+ || isPalin[i+][j-] == true)
isPalin[i][j] = true;
}
}
}
}
vector<vector<string>> partition(string s) {
buildMap(s);
vector<vector<string> > ret;
vector<string> cur;
Helper(ret, cur, s, );
return ret;
}
void Helper(vector<vector<string> >& ret, vector<string> cur, string s, int offset)
{
if(s == "")
ret.push_back(cur);
for(int i = ; i < s.size(); i ++)
{
if(isPalin[offset+][offset+i] == true)
{
cur.push_back(s.substr(, i+)); //palin prefix
Helper(ret, cur, s.substr(i+), offset+i+);
cur.pop_back();
}
}
}
};