← DSADSA 3.4
Tries
Not started yet — 6 problems queued. Word Search II (Recursion and Backtracking) is worth revisiting once this and backtracking are both solid.
A tree where each root-to-node path spells a prefix, giving O(L) prefix search/insert (L = word length) instead of scanning every word. Each node holds a children map plus an end-of-word flag.
Sub-patterns
- A — Prefix Search. Basic insert/search/startsWith.
- B — Word Dictionaries with Wildcards. Search supporting a wildcard character.
- C — Autocomplete-Style Aggregation. Collecting or counting words under a prefix.
Practice set (6)
- Medium — Implement Trie (Prefix Tree), Design Add and Search Words Data Structure, Replace Words
- Hard — Palindrome Pairs, Concatenated Words, Stream of Characters
Notes from readers
Comments — via GitHub