AdvancedChallenge 29 of 34

Trie autocomplete

Implement Trie with insert(word), contains(word) and starts_with(prefix), which returns every inserted word beginning with the prefix in alphabetical order. Store the words in a tree of dictionaries, one level per character.

Exercise

Trie autocomplete

4 checks

class Trie:
    def __init__(self):
        self.root = {}

    def insert(self, word):
        ...

    def contains(self, word):
        ...

    def starts_with(self, prefix):
        ...


t = Trie()
for w in ["maple", "mango", "matter", "melon", "peach"]:
    t.insert(w)
print(t.contains("mango"), t.contains("mat"))
print(t.starts_with("ma"))

Output

Press Run to try your code, then Check answer to grade it.