1233.
看起來就trie
多開一格放slash 才不會跟stop撞
不然a會卡ax...什麼什麼的
class Trie {
public:
vector<Trie*> ch;
bool stop;
Trie(): ch(27, nullptr), stop(false){};
// ch[26] = '/';
};
class Solution {
public:
Trie* root;
vector<string> removeSubfolders(vector<string>& folder) {
root = new Trie();
for(auto& s: folder){
Trie* t = root;
for(int i = 0; i < s.length(); i++){
if(s[i] == '/'){
if(t->stop) break;
if(t->ch[26] == nullptr){
t->ch[26] = new Trie();
}
t = t->ch[26];
continue;
}
if(t->ch[s[i]-'a'] == nullptr){
t->ch[s[i]-'a'] = new Trie();
}
t = t->ch[s[i]-'a'];
}
t->stop = true;
}
vector<string> res;
search_folder(root, "", res);
return res;
}
void search_folder(Trie* t, string folder, vector<string>& res){
if(t == nullptr) return ;
for(int i = 0; i < 26; i++){
search_folder(t->ch[i], folder + (char)('a' + i), res);
}
if(t->stop){
res.push_back(folder);
return;
}
else search_folder(t->ch[26], folder + '/', res);
}
};
跑好慢
看solution說有nlogn
才想到可以直接sort找
就看現在這個是不是上一個的subfolder
class Solution {
public:
vector<string> removeSubfolders(vector<string>& folder) {
ranges::sort(folder);
unordered_set<string> fs;
vector<string> res;
int len = folder[0].length();
for(auto& s: folder){
if(s.length() < len or s[len] != '/' or !fs.count(s.substr(0, len)) ){
fs.insert(s);
res.push_back(s);
len = s.length();
}
}
return res;
}
};
刷題這麼好玩
我都把daily當wordle在解
別人打LOL我寫扣
這種需要一點點思考的遊戲
本質差不多吧
打LOL比較難一點
※ 引述《Sougou (搜狗)》之銘言：
: 別再卷LeetCode了拉，
: 卷了對於求職也不見得有幫助，
: 對啊，
: 根據我之前碩畢拿offer經驗，
: 星國外商銀行IT一年有百萬，
: 面試還不是不看LeetCode，
: 考的是Java阿，
: 唉，
: 卷LeetCode不如去準備作品集==