Build a Trie for AutocompleteStep 1 of 5

Insert and Search

12345

Step 1: Insert and Search

A trie stores words as paths through a tree of characters. Shared prefixes share nodes, so "car" and "cart" walk the same first three steps. Each node marks whether a word ends there.

Implement:

  • insert(word): walk the tree character by character, creating nodes as needed, and mark the final node as the end of a word
  • search(word): return True only if the exact word was inserted (the path exists and its last node is marked a word)

The difference between "the path exists" and "a word ends here" is the whole trick. "car" being present doesn't mean "ca" is a word.

Hints
Starter code
class TrieNode:
    def __init__(self):
        self.children = {}      # char -> TrieNode
        self.is_word = False


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        """Add a word to the trie."""
        # TODO: walk from self.root, creating a child TrieNode for each missing
        # character, then set is_word = True on the final node.
        pass

    def search(self, word):
        """True only if the exact word was inserted."""
        # TODO: walk the path; if any char is missing return False;
        # otherwise return whether the final node's is_word is True.
        pass
Write it on a laptop

The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.

OverviewNext step