Faangprep Logo
Log inStart free
Browse curriculum

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

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

Interactive Visualization

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

Dry Run: startsWith('ap')

Trie has 'apple'.

Char Child Exists? Action
'a' Yes Move to 'a'.
'p' Yes Move to 'p'.
End - Loop done. Path exists. Return True.

Edge Cases & Checks

Important checks:

  • No Matches: Return valid value (false/empty list).

  • Empty Prefix: Matches every stored word: the loop never runs and startsWith returns true.

  • Case: Ensure 'A' doesn't match 'a' without normalization.

Solution (StartsWith Logic)

O(L) Time.

Prefix Matching Code
1Trie.prototype.startsWith = function(prefix) {
2    let node = this;
3    for(const char of prefix) {
4        if(!node.children[char]) return false;
5        node = node.children[char];
6    }
7    return true;
8};
Previous

Implement Trie (Prefix Tree)

The approach, step by step

  1. Start at the root

    Take the trie’s root as the current node.

  2. Follow each character

    For every character of the prefix, move to that child, or return false if it is missing.

  3. Return true

    If every character was found, the prefix path exists: return true.

Frequently asked questions

How does prefix matching work in a trie?

Start at the root and follow the child for each character of the prefix. If any child is missing, no stored word has that prefix; if the walk finishes, at least one does.

Why does startsWith ignore the end-of-word flag?

A prefix only needs its path to exist. The node where the walk stops may sit in the middle of a longer word, such as "ap" inside "apple", and it still counts as a match.

What is the time complexity of prefix matching in a trie?

O(L) time for a prefix of length L, since each character costs one child lookup, and O(1) extra space because the walk only keeps a reference to the current node.

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description