leetExpert

Module 20 · Tries

Practice

Practice~1 min

How to practice this module

Trie drills reward shared prefixes: an edge per character, an end marker per word. Implement-trie nails insert/search/startsWith; add-and-search adds wildcards; word-search-ii prunes a board walk with the trie; longest-word composes both. Done when all four show Solved in the hub.

Problems

Tries — work them in order; difficulty ascends.

0/4

solved

  1. 1Implement Trie (Prefix Tree)MediumInsert / walk / end markerWatch for: The end flag separates a word from a prefix — startsWith stops at the path, search requires the marker
  2. 2Design Add and Search Words Data StructureMediumWildcard DFSWatch for: A '.' must branch over every child; backtrack on mismatch and never prune the branch that might still match
  3. 3Longest Word in DictionaryMediumBuild and verify prefixesWatch for: A word is valid only if every prefix is a word — insert everything, then pick the longest whose prefixes all exist
  4. 4Word Search IIHardTrie-pruned board DFSWatch for: Advance the trie node with each board step and cut dead branches; restore the board mark after backtracking

Cheatsheet

Tries — Shared prefixes — search, autocomplete, and word breaks.

Smell → pattern

  • Many queries on shared stemsTrie insert + walk
  • Prefix exists?Stop mid-word
  • Word search on boardTrie + DFS prune

Patterns

Insert path

Core

Smell: Build a dictionary of words

Each character is an edge. Create missing children; mark end-of-word on the terminal node.

caend

Prefix walk

Safe

Smell: Autocomplete / startsWith

Follow characters until missing edge (fail) or path ends (prefix exists). End flag ⇒ full word.

caend

DFS with trie prune

Reach

Smell: Board word search with a dictionary

On a board, advance the trie node with each step; dead trie node ⇒ cut that branch early.

Complexity targets

  • Insert / search word

    Time
    O(L)
    Space
    O(Σ·L)
    Note
    L = word length

  • Build from dict

    Time
    O(total chars)
    Space
    O(total chars)
    Note
    Shares prefixes

Traps

  • Prefix vs word

    Reaching a node ≠ finding a word. Check the end marker (or count) explicitly.

  • Not restoring board marks

    In-place visited marks on a grid must be undone after DFS, or sibling paths see false walls.