Build a Trie for AutocompleteStep 3 of 5

Autocomplete

12345

Step 3: Autocomplete

The payoff: given a prefix, list every word that extends it. Walk to the prefix node, then depth-first collect every word beneath it.

  • words_with_prefix(prefix): return all inserted words starting with prefix, in sorted order (visit children in sorted character order)

If the prefix isn't present, return an empty list. An empty prefix returns every word in the trie.

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


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

    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_word = True

    def _find(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

    def words_with_prefix(self, prefix):
        """All inserted words starting with prefix, sorted."""
        # TODO:
        #   node = self._find(prefix)
        #   results = []
        #   if node is None: return results
        #   walk depth-first, visiting children in sorted order; when a node
        #   is_word, append prefix + the path collected so far.
        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.

PreviousNext step