abyiber.com
Back to Blog

Trie-Based String Problems

Use tries for autocomplete, word search, longest common prefix, and wildcard matching, with efficient prefix lookups and character-by-character traversal.

2025-09-26
Share
Coding Patternstriestringsleetcode

Terminology

Term Definition
Trie (prefix tree) A tree data structure where each node represents a character. Paths from root to nodes spell out prefixes. Enables $O(L)$ lookup where $L$ is the word length.
Trie node Contains a map of child characters and a boolean flag indicating whether this node marks the end of a complete word.
Prefix search Checking whether any word in the trie starts with a given prefix. Traverse the trie character by character; if you reach the end of the prefix without a dead end, the prefix exists.
Autocomplete Given a prefix, find all words that start with it. Navigate to the prefix node, then DFS to collect all words in the subtree.
Longest common prefix The longest string that is a prefix of all words in a set. In a trie, follow the path where each node has exactly one child until a branch or word-end is reached.
Wildcard matching Searching for words where some characters are wildcards (e.g., "." matches any character). Requires branching into all children at wildcard positions.
Word search (grid) Finding words from a dictionary in a 2D character grid. A trie prunes the search: if no word starts with the current path, stop exploring.

What & Why

A trie stores a set of strings so that any prefix lookup takes O(L) time, where L is the length of the query, regardless of how many strings are stored. This makes it ideal for autocomplete, spell checking, and prefix-based filtering.

Compared to a hash set (which gives O(L) exact lookup but no prefix support) or a sorted array (which gives O(L \log n) prefix search via binary search), a trie provides O(L) for both exact and prefix queries, plus the ability to enumerate all words sharing a prefix.

In LeetCode, tries appear in "implement trie," "word search II" (finding dictionary words in a grid), "longest common prefix," and "add and search word" (wildcard matching). The trie acts as a shared prefix tree that avoids redundant character comparisons.

How It Works

Trie Structure

Each node has up to 26 children (for lowercase English letters) and an isEnd flag. Inserting "cat" and "car" shares the "ca" prefix.

Trie containing: cat, car, card, cap * c c a a t r p t r p = end of word

Autocomplete

Navigate to the prefix node, then run DFS from that node to collect all complete words in the subtree. This gives all words starting with the prefix.

Wildcard Matching

When the query character is a wildcard (e.g., "."), branch into all existing children at that position. This turns a single traversal into a bounded DFS.

Complexity Analysis

Operation Time Space
Insert word $O(L)$ $O(L)$ new nodes worst case
Search exact word $O(L)$ $O(1)$
Prefix search $O(L)$ $O(1)$
Autocomplete (all matches) $O(L + M)$ where $M$ = total chars in results $O(M)$
Wildcard search $O(26^w \cdot L)$ where $w$ = wildcard count $O(L)$ recursion depth

Total space for a trie storing $n$ words of average length $L$ with alphabet size $|\Sigma|$:

$S = O(n \cdot L \cdot |\Sigma|)$ worst case, but shared prefixes reduce this significantly

Implementation

Basic Trie: Insert, Search, StartsWith

ALGORITHM TrieNode()
  children = map of character → TrieNode (initially empty)
  isEnd = FALSE
END

ALGORITHM Insert(root, word)
  node = root
  FOR EACH char IN word DO
    IF char NOT IN node.children THEN
      node.children[char] = new TrieNode()
    END IF
    node = node.children[char]
  END FOR
  node.isEnd = TRUE
END

ALGORITHM Search(root, word)
  node = root
  FOR EACH char IN word DO
    IF char NOT IN node.children THEN
      RETURN FALSE
    END IF
    node = node.children[char]
  END FOR
  RETURN node.isEnd
END

ALGORITHM StartsWith(root, prefix)
  node = root
  FOR EACH char IN prefix DO
    IF char NOT IN node.children THEN
      RETURN FALSE
    END IF
    node = node.children[char]
  END FOR
  RETURN TRUE
END

Autocomplete

ALGORITHM Autocomplete(root, prefix)
  INPUT: trie root, prefix string
  OUTPUT: list of all words starting with prefix

  node = root
  FOR EACH char IN prefix DO
    IF char NOT IN node.children THEN
      RETURN empty list
    END IF
    node = node.children[char]
  END FOR

  results = empty list
  DFS(node, prefix, results)
  RETURN results
END

ALGORITHM DFS(node, currentWord, results)
  IF node.isEnd THEN
    results.append(currentWord)
  END IF

  FOR EACH (char, child) IN node.children DO
    DFS(child, currentWord + char, results)
  END FOR
END

Wildcard Search (Add and Search Word)

ALGORITHM WildcardSearch(node, word, index)
  IF index = LENGTH(word) THEN
    RETURN node.isEnd
  END IF

  char = word[index]

  IF char = '.' THEN
    FOR EACH (c, child) IN node.children DO
      IF WildcardSearch(child, word, index + 1) THEN
        RETURN TRUE
      END IF
    END FOR
    RETURN FALSE
  ELSE
    IF char NOT IN node.children THEN
      RETURN FALSE
    END IF
    RETURN WildcardSearch(node.children[char], word, index + 1)
  END IF
END

Real-World Applications

  • Autocomplete and search suggestions: Google, IDE code completion, and phone keyboards use tries (or compressed variants like ternary search trees) for instant prefix matching.
  • Spell checkers: dictionaries stored as tries enable fast lookup and "did you mean?" suggestions by exploring nearby branches.
  • IP routing tables: longest prefix matching in network routers uses a bitwise trie to find the most specific route for an IP address.
  • Word games: Scrabble solvers and Boggle solvers use tries to prune invalid paths during board traversal.
  • Genome analysis: suffix tries and suffix trees index DNA sequences for fast substring and pattern matching.

Key Takeaways

  • Tries provide $O(L)$ insert, search, and prefix lookup regardless of how many words are stored, where $L$ is the query length
  • Shared prefixes save space: "cat," "car," "card," and "cap" share the "ca" path, storing only 7 nodes instead of 14 characters
  • Autocomplete navigates to the prefix node and DFS-collects all words in the subtree
  • Wildcard matching branches into all children at wildcard positions, bounded by the alphabet size per wildcard
  • For "word search II" on grids, build a trie from the dictionary and DFS the grid, pruning paths that do not match any trie prefix