Re: [閒聊] 每日leetcode
這題真的是
寫的非常不爽
簡單來說就是爆搜
dfs全部搜爆
或是bfs從大的開始搜
可是要記state
我選擇pruning==
太小我就不要了
class Solution {
public:
int maxUniqueSplit(string s) {
int len = s.length();
//string_view sv;
// C++20 hash:string_view
int res = 1;
for(int cut = (1 << (len - 1)) - 1; cut > 0; cut--){
//cout << "cut " << cut << '\n';
int head = 0;
unordered_set<string> st;
bool check = true;
int cnt = 1, c = cut;
while(c > 0){
cnt += c&1;
c >>= 1;
}
//cout << cnt << '\n';
if (cnt <= res) continue;
c = cut;
for(int i = 1; i < len and check ; i++, c >>= 1){
if(c & 1) {
check &= !st.count(s.substr(head, i - head));
//cout << head << " " << i << ", ";
st.insert(s.substr(head, i - head));
head = i;
}
}
if(!check) {
//cout << '\n';
continue;
}
check &= !st.count(s.substr(head, len - head));
//cout << head << " " << len << "; \n";
if(check){
res = cnt;
//cout << "res " << res << '\n';
}
}
return res;
}
};
嗎的真的要check 2^n 次真的超躁
莫名其妙
※ 引述《JIWP (神楽めあ的錢包)》之銘言：
: 1593. Split a String Into the Max Number of Unique Substrings
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.231.184.131 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1729517337.A.5BD.html
推
10/21 21:47,
1年前
, 1F
10/21 21:47, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 1018 之 1549 篇)：