Practice: Suggesting Commands From a Typed Prefix

A command line suggests every command that starts with what has been typed.

Pressing Tab in a shell, the program that reads typed commands, completes or lists every command starting with the letters typed, and a trie is a natural store for that list. This exercise covers building the trie for a set of commands and answering a typed prefix with every command below it, in alphabetical order.

A trie is a tree whose root holds no letter and whose every other node stands for one letter; a node carries an end-of-word mark when its path from the root spells a stored word.

The shell knows five commands: git, grep, go, gzip and ls.

Draw the trie that holds the five commands, marking the node that ends each one, and count its nodes below the root.
List the suggestions for the typed prefix g, then for gr, in alphabetical order.
Say what the suggestions are for x, and for an empty prefix.
Write a suggest(prefix) method that returns the list, in Python or a language of your choice.

The cost should depend on the prefix and the number of suggestions, not on how many commands the shell knows.

An answer: the trie, the suggestions and a listing

The trie has 12 nodes below the root. Four commands start with g, so they share one g node, which has four children; go ends one level down, on the o.

The trie holding git, grep, go, gzip and ls

root
- g
  - i
    - t, end of word: git
  - o, end of word: go
  - r
    - e
      - p, end of word: grep
  - z
    - i
      - p, end of word: gzip
- l
  - s, end of word: ls

suggest walks the prefix first and returns an empty list if a letter has no child, which is the answer for x. Otherwise it visits every node below the one it reached, children in letter order, and collects each marked path. For g that gives git, go, grep and gzip; for gr, only grep. An empty prefix walks nothing, stays at the root and returns all five. The walk costs one step per typed letter, and the collection one step per node below it, so adding a hundred commands starting with l would not slow the answer for gr.

suggest_commands.pypy

class Node:
    def __init__(self):
        self.children = {}
        self.is_word = False


class CommandTrie:
    def __init__(self, commands):
        self.root = Node()
        for command in commands:
            self.insert(command)

    def insert(self, command):
        node = self.root
        for letter in command:
            node = node.children.setdefault(letter, Node())
        node.is_word = True

    def suggest(self, prefix):
        node = self.root
        for letter in prefix:
            if letter not in node.children:
                return []
            node = node.children[letter]
        found = []
        self._collect(node, prefix, found)
        return found

    def _collect(self, node, text, found):
        if node.is_word:
            found.append(text)
        for letter in sorted(node.children):
            self._collect(node.children[letter], text + letter, found)


commands = CommandTrie(["git", "grep", "go", "gzip", "ls"])
for typed in ["g", "gr", "l", "x", ""]:
    print(f"typed {typed!r}: {commands.suggest(typed)}")

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

typed 'g': ['git', 'go', 'grep', 'gzip']
typed 'gr': ['grep']
typed 'l': ['ls']
typed 'x': []
typed '': ['git', 'go', 'grep', 'gzip', 'ls']

← → move through sections and cards