Trie/Prefix MatchingMedium

This practice workspace is built for desktop. Open it on a larger screen to start solving.

Prefix Matching

Trie·Medium

Given a list of strings words and a string prefix, return all words from words that start with prefix, sorted in ascending lexicographical order.

Matching is case-sensitive ('A' and 'a' are different characters). A word matches the empty prefix "". If no word matches, return an empty array.

This is the canonical Trie autocomplete primitive: build a trie from words, walk down the path spelled by prefix, then collect every complete word in the subtree rooted at that node.

Examples

Input: words = ["apple","app","apricot","banana"], prefix = "ap"

Output: ["app","apple","apricot"]

Three words start with 'ap'. Returned sorted lexicographically.

Input: words = ["dog","cat","bird"], prefix = "z"

Output: []

No word starts with 'z'.

Input: words = ["a","b","c"], prefix = ""

Output: ["a","b","c"]

Every word matches the empty prefix.

Constraints

0 <= words.length <= 10^4
0 <= words[i].length <= 100
0 <= prefix.length <= 100
words[i] and prefix consist of printable ASCII characters.
Matching is case-sensitive.

00:00Preview Mode (Read Only)

Loading editor…

Tests

Preview Mode

This is a read-only preview of DSAMind's AI coaching. Sign up to get custom feedback on your own solution.

Passed32 ms

First attempt — retry to track metric movement here.

Your approach

Pattern:Trie
Time:O(N)
Space:O(1)

Complete approach — pattern and complexity both named.

Coach

What you got right

You correctly matched the sorted input requirement and implemented a linear-time scan using two pointers.

Where it diverged

No divergence detected. The code correctly aligns with the stated approach.

Next attempt: focus on

Try solving related sliding window problems to build familiarity with two-pointer variants.

Signals

No signals fired — clean run, you stayed in flow.