LeetCode Tries Prefix Tree
10836 ワード
1 class TrieNode {
2 public:
3 const static int NR_FANOUT = 26;
4 TrieNode* child[NR_FANOUT];
5 int count;
6 // Initialize your data structure here.
7 TrieNode() {
8 for (int i=0; i<NR_FANOUT; i++) {
9 child[i] = NULL;
10 }
11 count = 0;
12 }
13 };
14
15 class Trie {
16 public:
17 Trie() {
18 root = new TrieNode();
19 }
20
21 // Inserts a word into the trie.
22 void insert(string s) {
23 insert(s, 0, root);
24 }
25
26 // Returns if the word is in the trie.
27 bool search(string key) {
28 return search(key, 0, root) != NULL;
29 }
30
31 // Returns if there is any word in the trie
32 // that starts with the given prefix.
33 bool startsWith(string prefix) {
34 return search_prefix(prefix, 0, root) != NULL;
35 }
36 private:
37 TrieNode* insert(string& s, int pos, TrieNode* current) {
38 int len = s.size();
39 if (pos > len) {
40 return NULL;
41 }
42 if (current == NULL) {
43 current = new TrieNode();
44 }
45 if (pos == len) {
46 current->count++;
47 return current;
48 }
49 int idx = s[pos] - 'a';
50 current->child[idx] = insert(s, pos + 1, current->child[idx]);
51 return current;
52 }
53
54 TrieNode* search(string& s, int pos, TrieNode* current) {
55 if (current == NULL) {
56 return NULL;
57 }
58 int len = s.size();
59 if (pos > len) {
60 return NULL;
61 } else if (pos == len && current->count) {
62 return current;
63 }
64 return search(s, pos + 1, current->child[s[pos] - 'a']);
65 }
66 TrieNode* search_prefix(string& s, int pos, TrieNode* current) {
67 if (current == NULL) {
68 return NULL;
69 }
70 int len = s.size();
71 if (pos >= len) {
72 return current;
73 }
74 return search_prefix(s, pos + 1, current->child[s[pos] - 'a']);
75 }
76 private:
77 TrieNode* root;
78 };
mplement a trie with
insert
, search
, and startsWith
methods. Note:You may assume that all inputs are consist of lowercase letters
a-z
.