Last Minute Notes
  • Github
  • Docs
  • Learn
    @sayanstwt
Lessons
0/15 done
  • Tree BFS
  • Tree DFS
  • Two Heaps
  • Top K Elements
  • K-way Merge
  • Trie
Learn/Data Structures & Algorithms/Trees & Heaps

Trie

7 min Intermediate 7 steps

Share prefixes to search words and autocomplete fast.

Words
4
Checked
0
Matches
0
appleappaptbatapprefixwhich words start with "ap"?
current end of word walked path
In this lessonStep 1 of 7
  1. The problem
  2. Shared paths
  3. Insert
  4. Search
  5. More words
  6. Cost
  7. Recap
Step 1 / 7problem

Prefix queries over a word list

Which words start with "ap"? With a plain list, every query compares against every word.

Autocomplete runs that query on every keystroke.

Key idea

Prefix search, autocomplete, word dictionary: think trie.

←→ step·R replay·Space pause

You'll learn

  • See why scanning a word list for prefixes does not scale
  • Insert a word one character edge at a time
  • Tell search apart from startsWith
  • Answer prefix queries in O(L), independent of word count
Read the full notesDSA Pattern Playbook, 6.5