aboutsummaryrefslogtreecommitdiff
path: root/trie_prefix.cpp
blob: b56e38b6a2e3a8d4c314719c1e996e4f4789f117 (plain)
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
// 208. Implement Trie (Prefix Tree)
#include "leetcode.h"

class Trie {
public:
  Trie() {}
  void insert(string word) {
    Trie *node = this;
    for (char c : word) {
      if (!node->next.count(c))
        node->next[c] = new Trie();
      node = node->next[c];
    }
    node->is_word = true;
  }
  bool search(string word) {
    Trie *node = this;
    for (char c : word) {
      if (!node->next.count(c))
        return false;
      node = node->next[c];
    }
    return node->is_word;
  }
  bool startsWith(string prefix) {
    Trie *node = this;
    for (char c : prefix) {
      if (!node->next.count(c))
        return false;
      node = node->next[c];
    }
    return true;
  }

private:
  map<char, Trie *> next = {};
  bool is_word = false;
};

int main() {
  Trie *obj = new Trie();
  obj->insert("Trie");
  bool param_2 = obj->search("Trie");
  bool param_3 = obj->startsWith("Trie");
}