Build a Trie for AutocompleteStep 2 of 5

Prefix Matching

12345

Step 2: Prefix Matching

Autocomplete needs to know whether any word starts with a given prefix, even if the prefix itself isn't a word. Factor out the walk into a helper and add the prefix check.

  • _find(prefix): return the node at the end of the prefix path, or None if the path breaks
  • starts_with(prefix): True if any inserted word begins with this prefix (i.e. the path exists)

Rewrite search in terms of _find too, it's just "_find succeeded and the node is a word".

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):
        """Return the node at the end of prefix, or None if the path breaks."""
        # TODO: walk from root; return None if a char is missing; else the node.
        pass

    def search(self, word):
        node = self._find(word)
        return node is not None and node.is_word

    def starts_with(self, prefix):
        """True if any inserted word begins with prefix."""
        # TODO: return whether self._find(prefix) is not None
        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