力扣208. 实现 Trie (前缀树)

 1 class Trie:
 2 
 3     def __init__(self):
 4         """
 5         Initialize your data structure here.
 6         """
 7         self.trie = set()
 8 
 9     def insert(self, word: str) -> None:
10         """
11         Inserts a word into the trie.
12         """
13         self.trie.add(word)
14 
15     def search(self, word: str) -> bool:
16         """
17         Returns if the word is in the trie.
18         """
19         return word in self.trie
20 
21     def startsWith(self, prefix: str) -> bool:
22         """
23         Returns if there is any word in the trie that starts with the given prefix.
24         """
25         lens = len(prefix)
26         for s in self.trie:
27             if s[:lens] == prefix:
28                 return True
29         return False
30 
31 
32 # Your Trie object will be instantiated and called as such:
33 # obj = Trie()
34 # obj.insert(word)
35 # param_2 = obj.search(word)
36 # param_3 = obj.startsWith(prefix)

 1 class Trie {
 2 private:
 3     bool isEnd;
 4     Trie* next[26];
 5 public:
 6     Trie() {
 7         isEnd = false;
 8         memset(next, 0, sizeof(next));
 9     }
10     
11     void insert(string word) {
12         Trie* node = this;
13         for (char c : word) {
14             if (node->next[c-‘a‘] == NULL) {
15                 node->next[c-‘a‘] = new Trie();
16             }
17             node = node->next[c-‘a‘];
18         }
19         node->isEnd = true;
20     }
21     
22     bool search(string word) {
23         Trie* node = this;
24         for (char c : word) {
25             node = node->next[c - ‘a‘];
26             if (node == NULL) {
27                 return false;
28             }
29         }
30         return node->isEnd;
31     }
32     
33     bool startsWith(string prefix) {
34         Trie* node = this;
35         for (char c : prefix) {
36             node = node->next[c-‘a‘];
37             if (node == NULL) {
38                 return false;
39             }
40         }
41         return true;
42     }
43 };