Re: [閒聊] 每日leetcode

[oin1104 (是oin的說)]

題目

看甚麼字串是其他字串的子字串


思路

字典樹插入後綴時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: 臨摹圖不用一起發嗎?
推 DJYOMIYAHINA: 大師
→ Furina: 大師
→ Meaverzt: 大師