[前缀树]leetcode1032：字符流(hard)_字节hard算法题

题目：

题解：
起初使用前缀树导致内存爆了，后改用后缀树顺利通过，不过就是时间有点吃不消了。（后缀树就是每个字符串反向后建立的前缀树，本质还是前缀树。）

解题思路：

• 1）从words中提取word，将word反向，建立后缀树。
• 2）在查询的时候，我们将每个字符保存在一个字符串中，每次每个字符都插入到该字符串的首部。然后我们直接在后缀树中查找该字符串的最短前缀能否表示成一个字符串就行了。

代码如下：

class Trie{
private:
    bool is_string=false;
    Trie* next[26]={nullptr};
public:
    Trie(){}
    void insert(string& word){
        Trie* root=this;
        for(const auto& w:word){
            if(root->next[w-'a']==nullptr)root->next[w-'a']=new Trie();
            root=root->next[w-'a'];
        }
        root->is_string=true;
    }
    //word的最短前缀是否在后缀树中
    bool startsWith(string& word){
        Trie* root=this;
        for(const auto& w:word){
            if(root->next[w-'a']!=nullptr){
                root=root->next[w-'a'];
                if(root->is_string)return true;
            }
            else return false;
        }
        return false;
    }
};
class StreamChecker {
private:
    Trie* root;
    string word;
public:
    StreamChecker(vector<string>& words) {
        root=new Trie();
        for(auto word:words){
            reverse(word.begin(),word.end());//反向字符串
            root->insert(word);
        }
    }
    
    bool query(char letter) {
        Trie* note=root;
        word.insert(word.begin(),letter);//讲letter插入到word的前面
        return note->startsWith(word);
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47