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 };