Re: [閒聊] 每日leetcode已回收
改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--){
: if(s[i] != s[j]) return false;
: }
: return true;
: }
: // cut into 2 substring
: // check isPa
: void cut(string s, vector<vector<string>>& res, vector<string> v){
: if(s == ""){
: res.push_back(v);
: return;
: }
: for(int i = 1; i <= s.length(); i++){
: string t = s.substr(0, i);
: if( isPa(t) ){
: v.push_back(t);
: cut(s.substr(i, s.length() -i ), res, v);
: v.pop_back();
: }
: }
: return;
: }
: };
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.231.168.210 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1716410914.A.976.html
推
05/23 05:30,
1年前
, 1F
05/23 05:30, 1F
推
05/23 08:08,
1年前
, 2F
05/23 08:08, 2F
→
05/23 09:20,
1年前
, 3F
05/23 09:20, 3F
討論串 (同標題文章)
完整討論串 (本文為第 264 之 1553 篇)：