Autocomplete

autocompleteproblem-labtrieprefixstrings

Saved on this device

Full lesson · 8 learning steps Open any exercise for focused practice

Step 1 of 8 · intro card

Learn Autocomplete

Data Challenges

A trie stores words as a tree of characters so shared prefixes share a path. Insert each word character by character, then walk to a prefix node and gather every word below it to suggest completions.

The scenario: as a user types, you want to suggest every stored word that starts with what they have typed so far.

A trie inserts each word one character at a time, creating child nodes for new letters and reusing existing ones, so all words sharing a prefix share the same path down the tree.

To autocomplete, walk from the root following the prefix characters; if the path exists, do a depth-first collection of every word ending beneath that node.

insert adds a word character by character.

Shared prefixes share a single path.

wordsWithPrefix walks to the prefix node and collects below it.

class Trie {
  constructor() {
    this.root = {}
  }
  insert(word) {
    let node = this.root
    for (const ch of word) {
      node[ch] ??= {}
      node = node[ch]
    }
    node.end = true
  }
  wordsWithPrefix(prefix) {
    let node = this.root
    for (const ch of prefix) {
      if (!node[ch]) return []
      node = node[ch]
    }
    const out = []
    const walk = (n, acc) => {
      if (n.end) out.push(prefix + acc)
      for (const ch in n) {
        if (ch !== "end") walk(n[ch], acc + ch)
      }
    }
    walk(node, "")
    return out
  }
}

Read the implementation

Connect each part of the code to the concept before you type.

1. Insert a word

insert walks one character at a time, creating a child node for each new letter.

insert(word) {

2. Create child node

Each character becomes a child key, so shared prefixes share the same path.

node[ch] ??= {}

3. Mark word end

An end flag marks where a full word terminates, distinguishing words from mere prefixes.

node.end = true

4. Walk to prefix

wordsWithPrefix descends to the prefix node, then collects every word beneath it.

wordsWithPrefix(prefix) {

A complete learning loop

Understand

Read the concept map and follow the code breakdown.

Reconstruct

Type the implementation, repair mistakes and work through every recall exercise.

Verify

Use the final check without hints; revisit weak concepts in short practice sessions.