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"]
]
思路：先用dict[i][j]保存string的下标从i到j是否是回文。可用DFS方法求解。
class Solution {
public:
void partitionHelper(int start, int pos, vector<vector<bool> > &dict, vector<vector<string> >&res, vector<string>&perRes, string str) {
if(start == str.length()) {
if (!perRes.empty()) {
res.push_back(perRes);
}
return;
}
int j;
for(j=0; start+j<str.length(); ++j) {
if(dict[start][start+j]) {
perRes.resize(pos+1);
string s(str.substr(start,j+1));
perRes[pos] = s;
partitionHelper(start+j+1,pos+1,dict,res,perRes,str);
}
}
}
vector<vector<string> > partition(string s) {
vector<vector<string> > res;
res.clear();
if (s.empty()) {
return res;
}
vector<vector<bool> > dict(s.length(), vector<bool>(s.length(),false));
int n = s.size();
int i,j,k1,k2;
for(i=0; i<n; ++i) {
dict[i][i] = true;
for(j=i+1; j<n; ++j) {
k1 = i, k2 = j;
while(k1 < k2 && s[k1]==s[k2]) {
k1++,k2--;
}
if (k1>=k2) {
dict[i][j] = true;
}
}
}
vector<string> perRes;
partitionHelper(0,0,dict,res,perRes,s);
return res;
}
};