{ }SolveLog
⌕
Home / Patterns / Trie
10 worked problems

Trie

Prefix trees for words and bits. Many words or bit strings share prefixes and queries repeatedly walk those prefixes.

Recognition signal

When should you think of Trie?

Many words or bit strings share prefixes and queries repeatedly walk those prefixes.

Core invariant

What must stay true?

The current trie node represents the exact prefix consumed so far.

Practice in a deliberate order

Starter

Build the template

  1. No starter problem is published yet.
Core

Recognize variations

  1. #208 Implement Trie (Prefix Tree)Medium
  2. #211 Design Add and Search Words Data StructureMedium
  3. #648 Replace WordsMedium
  4. #677 Map Sum PairsMedium
  5. #720 Longest Word in DictionaryMedium
  6. GFG Longest Word with All PrefixesMedium
Stretch

Combine ideas under pressure

  1. #212 Word Search IIHard
  2. #421 Maximum XOR of Two Numbers in an ArrayHard
  3. #1707 Maximum XOR With an Element From ArrayHard
  4. GFG Number of Distinct SubstringsHard

What to learn in this cluster

  1. 01Insert and prefix lookup
  2. 02Wildcard and board search
  3. 03Bitwise tries for maximum XOR

All Trie problems

10 of 10 walkthroughs
Continue the cluster

Related patterns and study guides

Strings →Recursion & Backtracking →Bit Manipulation →
Language choicePython vs C++ vs Java: which language should you use for DSA?Coding habitsHow to code effectively: a repeatable workflow from idea to solutionLearning strategyHow to practice LeetCode without memorizing solutions