Inserts a word in the trie. Starting from the root, move down the trie following the path of characters in the word. If the nodes for the word characters end, add them. When the last char is added, mark it as a word-ending node.
(self, word)
| 16 | self.root = Node('') #The root of the trie is always empty |
| 17 | |
| 18 | def insert(self, word): |
| 19 | """ |
| 20 | Inserts a word in the trie. Starting from the root, move down the trie |
| 21 | following the path of characters in the word. If the nodes for the word |
| 22 | characters end, add them. When the last char is added, mark it as a |
| 23 | word-ending node. |
| 24 | """ |
| 25 | l = len(word) |
| 26 | curr = self.root |
| 27 | for i, c in enumerate(word): |
| 28 | last = False |
| 29 | if(i == l-1): |
| 30 | #The last char of the word |
| 31 | last = True |
| 32 | |
| 33 | if(c not in curr.children): |
| 34 | curr.children[c] = Node(c, curr, last) |
| 35 | elif(last): |
| 36 | #c already exists, but as it is the last char of word, |
| 37 | #it should now be flagged as a word in the trie. |
| 38 | curr.children[c].word = True |
| 39 | |
| 40 | curr = curr.children[c] |
| 41 | |
| 42 | def search(self, word): |
| 43 | """ |