Chapter 17
These are the solutions to the exercises found in the section .
-
This trie stores the words: “tag”, “tan”, “tank”, “tap”, “today”, “total”, “we”, “well”, and “went”.
-
Here is a trie that stores the words “get”, “go”, “got”, “gotten”, “hall”, “ham”, “hammer”, “hill”, and “zebra”:
-
The following code starts at the trie’s node and iterates over each of its children. For each child, it prints the key and then recursively calls itself on the child node:
def traverse(self, node=None): current_node = node or self.root for key, child_node in current_node.children.items(): print(key) if key != "*": self.traverse(child_node) -
Our autocorrect implementation is a combination of the search and collect_all_words functions:
def autocorrect(self, word): current_node = self.root word_found_so_far = "" for char in word: if current_node.children.get(char): word_found_so_far += char current_node = current_node.children.get(char) else: return word_found_so_far + \ self.collect_all_words([], current_node)[0] return word The basic approach is that we first search the trie to find as much of the prefix as we can. When we hit a dead end, instead of just returning None (as the search function does), we call collect_all_words on the current node to collect all the suffixes that stem from that node. We then use the first suffix of the array and concatenate it with the prefix to suggest a new word to the user.
