FAANGPrep Sprint

Prefix Matching

Use Trie to efficiently find all keys matching a prefix.

Medium

Problem Understanding

This is essentially startsWith but often implies retrieving related data or completing the word. In this lesson, we use the standard startsWith logic as the core building block for Autocomplete systems.

Algorithm Strategy

Start at the Trie root.
Iterate through each character of the prefix.
Check if the current node has a child for that character.
If No: Prefix doesn't exist. Return False.
If Yes: Move to that child node.
If loop completes: The path exists. Return True (unlike Search, we ignore isEnd).

Interactive Visualization

PREFIX "ap" · GREEN = END OF A STORED WORD

TRIE BUILT

Checked

Depth

Returns

—

The trie holds "apple", "apply", "apt", "bat"

startsWith("ap"): start at the root

Words

Prefix

See how startsWith confirms if a path exists without requiring the isEnd flag.

Previous Problem

Implement Trie (Prefix Tree)

Next Problem

Subarray Sum Equals K