Step 4 of 4

Auto-Complete Suggestions

You start from the build so far — your own work where you have written it, the reference build where you have not. Either way this step stands on its own.

Search engines and code editors use Tries to power type-ahead suggestions.

Implement autocomplete(prefix):

  1. Traverse down to the node representing the end of prefix. If the prefix does not exist, return an empty array/list [].
  2. Run a depth-first search (DFS) starting from that node down the subtree.
  3. Whenever a node with isEndOfWord === true is encountered, append the accumulated word to the results.
  4. Return all completed words matching the prefix.

Your build

Running is free — Submit is what records the step. Or press ⌘↩

Tests

1 case
calltypeexpectedresult
runOps([["insert","cat"],["insert","car"],["insert","card"],["insert","care"],["insert","dog"],["autocomplete","car"],["autocomplete","ca"],["autocomplete","z"]])collects all words matching a prefix[null,null,null,null,null,["car","card","care"],["car","card","care","cat"],[]]—

Hints

Stuck? Hints open one at a time, each giving a little more away.

3 hints left