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"] ]Subscribe to see which companies asked this question
class Solution { private: bool ispar(const string & s,int begin, int end) { for(int i=begin,j=end;i<j;) if(s[i++]!=s[j--]) return false; return true; } void backtrack(const string &s,int begin,vector<string> temp,vector<vector<string>>& ans) { if(begin==s.size()) { ans.push_back(temp); return ; } else { for(int i=begin;i<s.size();++i) { if(ispar(s,begin,i)==true) { temp.push_back(s.substr(begin,i-begin+1));//注意substr的第二个参数表示长度 backtrack(s,i+1,temp,ans); temp.pop_back(); } } return ; } } public: vector<vector<string>> partition(string s) { vector<vector<string>> ans; vector<string> temp; backtrack(s,0,temp,ans);//注意没有迭代。 return ans; } };