解法一.
class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string> > res;
vector<string> cur;
DFS(res, cur, s, );
return res;
}
void DFS(vector<vector<string> >& res, vector<string>& cur, string s, int start)
{
if(start >= s.size())
{
res.push_back(cur);
return ;
}
for(int i = start; i < s.size(); i++)
{
if(ispalindrome(s, start, i))
{
cur.push_back(s.substr(start, i-start+));
DFS(res, cur, s, i+);
cur.pop_back();
}
}
}
bool ispalindrome(string s, int start, int end)
{
while(start < end)
{
if(s[start++] != s[end--])
return false;
}
return true;
}
};对于解法一，每次要求是否为回文串导致时间效率降低
解法二使用DP先求出回文串，然后直接DFS效率会高一点，可是空间效率会降低
class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string> > res;
vector<string> cur;
vector<vector<bool> > dp(s.size(), vector<bool>(s.size(), false));
getDP(dp, s);
DFS(res, cur, s, , dp);
return res;
}
void DFS(vector<vector<string> >& res, vector<string>& cur, string s, int start, vector<vector<bool> >& dp)
{
if(start >= s.size())
{
res.push_back(cur);
return ;
}
for(int i = start; i < s.size(); i++)
{
if(dp[start][i])
{
cur.push_back(s.substr(start, i-start+));
DFS(res, cur, s, i+, dp);
cur.pop_back();
}
}
}
void getDP(vector<vector<bool> >& dp, string s)
{
for(int i = ; i < dp.size(); i++)
{
for(int j = i, k = ; j < dp.size(); j++, k++)
{
if(abs(j-k) <= )
dp[k][j] = s[k] == s[j] ? true : false;
else
dp[k][j] = (dp[k+][j-])&&(s[k] == s[j]);
}
}
}
};小白欢迎各位大神指点