Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
Example:
Input: "aab"
Output:
[
["aa","b"],
["a","a","b"]
]
题目大意:
对给出的字符串,找出回文字符串的所有组合的方式。
解题思路:
DFS即可,每次开始位置为上一个回文字符串的结束位置。
class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> ans;
vector<string> tmp;
helper(s, 0, ans, tmp);
return ans;
}
void helper(string s, int begin, vector<vector<string> >& ans, vector<string >& tmp){
if(begin==s.size()){
ans.push_back(tmp);
return;
}
for(int i=begin; i < s.size();i++){
string cor_s = s.substr(begin, i-begin+1);
if(valid(cor_s)){
// cout << cor_s << endl;
tmp.push_back(cor_s);
helper(s, i+1, ans, tmp);
tmp.pop_back();
}
}
}
bool valid(string s){
for(int i =0;i<int(s.size()/2);i++){
if(s[i]!=s[s.size()-1-i]) return false;
}
return true;
}
};