Cinte's Leetcode Record
0%

208. Implement Trie (Prefix Tree)

Posted on Edited on In Disqus:
Symbols count in article: 5.7k Reading time ≈ 5 mins.

208. Implement Trie (Prefix Tree)

使用vector
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
class Trie {
public:
    /** Initialize your data structure here. */
    Trie() {
        root = new Node();
    }
    
    /** Inserts a word into the trie. */
    void insert(string word) {
        int start = -1;
        Node* point = root;        
        while(++start < word.size())
        {
            if(!travesalChilds(word, start, point))
            {
                point->childs.push_back(new Node(word[start]));
                point = point->childs.back(); 
            }
        }
        point->endOfWord = true;
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
        Node* point = root;
        int start = -1;
        while(++start < word.size())
        {
            if(!travesalChilds(word, start, point))
                return false;
        }
        return point->endOfWord;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        Node* point = root;
        int start = -1;
        while(++start < prefix.size())
        {
            if(!travesalChilds(prefix, start, point))
                return false;
        }
        return true;   
    }
private:
    struct Node {
        bool endOfWord = false;
        char val;
        vector<Node*> childs;
        Node() = default;
        Node(char val, bool end = false) : val(val), endOfWord(end) {};
    };
    Node* root;
    bool travesalChilds(string& s, int& start, Node*& node)
    {
        for(auto& child : node->childs)
        {
            if(child->val == s[start])
            {
                node = child;
                return true;
            }
        }
        return false;
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */
使用hashmap
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class Trie {
public:
    /** Initialize your data structure here. */
    Trie() {
        root = new Node();
    }
    
    /** Inserts a word into the trie. */
    void insert(string word) {
        int start = -1;
        Node* point = root;        
        while(++start < word.size())
        {
            if(point->childs.find(word[start]) != point->childs.end())
                point = point->childs[word[start]];
            else
                point = point->childs.insert({word[start] ,new Node(word[start])}).first->second;
        }
        point->endOfWord = true;
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
        Node* point = root;
        int start = -1;
        while(++start < word.size())
        {
            if(point->childs.find(word[start]) != point->childs.end())
                point = point->childs[word[start]];
            else
                return false;
        }
        return point->endOfWord;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        Node* point = root;
        int start = -1;
        while(++start < prefix.size())
        {
            if(point->childs.find(prefix[start]) != point->childs.end())
                point = point->childs[prefix[start]];
            else
                return false;
        }
        return true;   
    }
private:
    struct Node {
        bool endOfWord = false;
        char val;
        unordered_map<char ,Node*> childs;
        Node() = default;
        Node(char val, bool end = false) : val(val), endOfWord(end) {};
    };
    Node* root;
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */
使用数组
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class Trie {
public:
    /** Initialize your data structure here. */
    Trie() {
        root = new Node();
    }
    
    /** Inserts a word into the trie. */
    void insert(string word) {
        int start = -1;
        Node* point = root;        
        while(++start < word.size())
        {
            if(point->childs[word[start] - 'a'] != nullptr)
                point = point->childs[word[start] - 'a'];
            else
            {
                point->childs[word[start] - 'a'] = new Node(word[start]);
                point = point->childs[word[start] - 'a'];
            }
        }
        point->endOfWord = true;
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
        Node* point = root;
        int start = -1;
        while(++start < word.size())
        {
            if(point->childs[word[start] - 'a'] != nullptr)
                point = point->childs[word[start] - 'a'];
            else
                return false;
        }
        return point->endOfWord;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        Node* point = root;
        int start = -1;
        while(++start < prefix.size())
        {
            if(point->childs[prefix[start] - 'a'] != nullptr)
                point = point->childs[prefix[start] - 'a'];
            else
                return false;
        }
        return true;   
    }
private:
    struct Node {
        bool endOfWord = false;
        char val;
        Node* childs[26]{ nullptr };
        Node() = default;
        Node(char val, bool end = false) : val(val), endOfWord(end) {};
    };
    Node* root;
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */
review
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
48
49
50
51
52
53
54
55
56
class Trie {
public:
    Trie() : head(new Node()) {

    }
    
    void insert(string word) {
        auto point = head;
        for(auto ch : word)
        {
            if(!point->childs[ch - 'a'])
                point->childs[ch - 'a'] = new Node();
            point = point->childs[ch - 'a'];
        }
        point->isWord = true;
    }
    
    bool search(string word) {
        auto point = head;
        for(auto ch : word)
        {
            if(!point->childs[ch - 'a'])
                return false;
            point = point->childs[ch - 'a'];
        }
        return point->isWord;
    }
    
    bool startsWith(string prefix) {
        auto point = head;
        for(auto ch : prefix)
        {
            if(!point->childs[ch - 'a'])
                return false;
            point = point->childs[ch - 'a'];
        }
        return true;
    }
private:
    struct Node
    {
        Node* childs[26]{};
        bool isWord;
        Node() : isWord(false) {}
    };
private:
    Node *head;
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */