改dp先记回文
变胖又变慢 操你妈的
class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> res;
int n = s.length();
vector<vector<bool>> dp (n, vector<bool>(n, false));
for(int i = 0; i< n; i++){
for(int j = 0; j<= i; j++){
if(s[j] == s[i] and ( ((i-j) <= 2) or dp[j+1][i-1]) ){
dp[j][i] = true;
}
}
}
for(int i = 0; i< n ;i++){
for(int j = 0; j< n ;j++){
cout << (int)dp[j][i];
}
cout << endl;
}
cut(s, res, {}, dp, 0);
return res;
｝
// cut into 2 substring
// check isPa
void cut(string s, vector<vector<string>>& res, vector<string> v, vector<vector<bool>>& dp, int offset){
if(s == ""){
res.push_back(v);
return;
}
for(int i = 1; i <= s.length(); i++){
if( dp[offset][offset +i-1] ){
v.push_back(s.substr(0, i));
cut(s.substr(i, s.length() -i ), res, v, dp, offset +i );
v.pop_back();
}
}
return;
}
};
※ 引述《sixB (6B)》之铭言：
: 131. 怕拎奘 切切切
: 超讨厌回文==写起来超不奘的
: 写出来都看起来超笨超慢超级烧空间
: 我的问题：（
: class Solution {
: public:
: vector<vector<string>> partition(string s) {
: vector<vector<string>> res;
: cut(s, res, {});
: return res;
: }
: bool isPa(string& s){
: for(int i = 0, j = s.length() -1; i < j; i++, j