131. Palindrome Partitioning
Description
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"]
]
Analysis
思路比较简单，只需要先检查(start,i)区间内是否为回文串，如果是，则令start自增1后，进行递归即可，代码如下:
code
class Solution {
private:
bool isPalindrome(const string & s,int start,int end){
while(start<end){
if(s[start++]!=s[end--])
return false;
}
return true;
}
void backtracking(vector<vector<string>> & res,vector<string> & temp,string & s,int start){
if(start==s.size()){
res.push_back(temp);
return;
}
for(int i=start;i<s.size();++i){
if(isPalindrome(s,start,i)){
temp.push_back(s.substr(start,i-start+1));
backtracking(res,temp,s,i+1);
temp.pop_back();
}
}
}
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> res;
vector<string> temp;
backtracking(res,temp,s,0);
return res;
}
};