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"]
]
class Solution {
public:
void DFS(string &s,vector<string> &path,vector<vector<string>> &result,int start)
{
if(start == s.size())
{
result.push_back(path);
return;
}
for(int i=start;i<s.size();i++)
{
if(isPalindrome(s,start,i))
{
path.push_back(s.substr(start,i-start+1));
DFS(s,path,result,i+1);//不是所有的字符都参与循环
path.pop_back();
}
}
}
bool isPalindrome(string &s,int start,int end)
{
while(start < end&&s[start] == s[end])
{
start++;
end--;
}
if(start>=end)
return true;
else
return false;
}
vector<vector<string>> partition(string s) {
vector<vector<string>> result;
vector<string> path;
DFS(s,path,result,0);
return result;
}
};
