Tries

Prefix trees for fast autocomplete, dictionary lookup, and word search.

Tries Practice Problems

Easy

4 problems
  1. 460

    Implement Trie (Prefix Tree)

    Build a tree of letters that can store words and answer both "is this an exact word?" and "does any word start like this?".

    easy
  2. 461

    Longest Common Prefix

    Find the longest beginning that every word shares by walking down a trie until the path splits or a word ends.

    easy
  3. 462

    Index Pairs of a String

    Report the start and end position of every place a dictionary word appears inside a string, using a trie to stop dead ends early.

    easy
  4. 463

    Longest Word in Dictionary

    Find the longest word that can be built one letter at a time, where every step along the way is also a word in the list.

    easy

Medium

4 problems
  1. 464

    Replace Words

    Swap each word in a sentence for the shortest dictionary root that starts it, found by walking the word down a trie of roots.

    medium
  2. 465

    Design Add and Search Words Data Structure

    Store words in a trie and support searches where a dot stands for any single letter, by trying every branch at a dot.

    medium
  3. 466

    Map Sum Pairs

    Keep a running total on every trie node so the sum of all values whose key starts with a prefix is a single lookup.

    medium
  4. 467

    Search Suggestions System

    Show up to three matching products after each letter typed, by caching the best three answers on every trie node.

    medium

Hard

2 problems
  1. 468

    Stream of Characters

    Answer after every arriving letter whether the stream now ends with one of the stored words, using a trie of reversed words.

    hard
  2. 469

    Concatenated Words

    Find every word that is made by gluing together two or more shorter words from the same list, using a trie to try each split point.

    hard

Related concepts