Re: [閒聊] 每日leetcode

看板Marginalman作者oin1104 (是oin的說)時間11月前 (2025/01/07 22:23)推噓2(2推 0噓 2→)

題目看甚麼字串是其他字串的子字串思路字典樹插入後綴時val++ 查詢時如果val>1就代表有其他字的子字串是他這個做法如果我可以O1插入後綴的話應該會比較快但是後綴樹的那個演算法我不會所以算了 ```cpp class TrieTree { TrieTree* child[128]; public: int val; TrieTree(): val(0), child{0} { } TrieTree* get(char c) { if(!child[c]) child[c] = new TrieTree(); return child[c]; } TrieTree* get(const string& s) { TrieTree* t = this; for(char c: s) { t = t->get(c); t->val ++; } return t; } TrieTree* find(char c) { return child[c]; } TrieTree* find(const string& s) { TrieTree* t = this; for(char c: s) { t = t->find(c); if(!t) break; } return t; } }; class Solution { public: vector<string> stringMatching(vector<string>& words) { TrieTree *save = new TrieTree(); int n = words.size(); vector<string> res; for(int i = n-1 ; i >= 0 ; i --) { for(int j = 0 ; j < words[i].size() ; j ++) { save->get(words[i].substr(j)); } } for(int i = n-1 ; i >= 0 ; i --) { if(save->find(words[i]) && save->find(words[i])->val>1)res.push_back (words[i]); } return res; } }; ``` -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.228.169.39 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1736259781.A.1B1.html

推

mrsonic

01/07 22:25, 11月前 , 1^F

01/07 22:25, 1^F

推

DJYOMIYAHINA

01/07 22:28, 11月前 , 2^F

01/07 22:28, 2^F

→

Furina

01/07 23:02, 11月前 , 3^F

01/07 23:02, 3^F