• 1 <= word.length, prefix.length <= 2000
• word and prefix consist only of lowercase English letters
• At most 3 × 10⁴ calls in total to insert, search and startsWith
• The same word may be inserted more than once; duplicates change nothing
• search and startsWith may be called before any insert

Before designing anything, notice which of the three operations is actually hard. Exact insertion and exact search are things a hash set already does well. The awkward one is startsWith, and every design decision below exists to serve it.

Put a million words in a hash set. Now answer: does any stored word begin with "pre"?

A hash set finds a key by running it through a hash function to get a storage slot. That is what makes lookup fast, and it is also what makes this question impossible to answer quickly. Hashing deliberately scrambles — "pre", "pref" and "prefix" land in three unrelated slots with no relationship between them. Knowing where "pre" would live tells you nothing about where words starting with "pre" live.

So the only option is to examine every stored word:

def starts_with(prefix):
    for word in words:                 # every single word
        if word.startswith(prefix):
            return True
    return False

That is O(N × L) per query — a million comparisons to answer one prefix question, repeated for every query.

Name the waste precisely: the structure throws away the relationship between a word and its prefixes, then pays to rediscover it on every query. And the relationship is not incidental — "apple", "apply" and "app" genuinely share their first three characters, a fact the set records three separate times and can never exploit.

Here is the change in viewpoint. Stop storing strings as values sitting in slots. Store each string as a route through a tree, one edge per character.

Build a tree whose root means "the empty prefix". Each edge is labelled with a character, and following a route from the root spells out a string. So a node is not a character — a node is a prefix, namely the string spelled by the route that reaches it.

Insert "cat": from the root take the c edge, then a, then t, creating nodes as needed. Insert "car": the c and a edges already exist, so reuse them and branch only at the final letter. Shared prefixes are stored exactly once and become shared structure.

Now look at what the hard operation costs. To answer startsWith("ca"), walk c then a from the root. If you arrive somewhere, at least one word passes through that node, so the answer is true. If any edge is missing, the answer is false. That is two steps regardless of whether the tree holds ten words or ten million.

This structure is a trie, from retrieval, also called a prefix tree.

There is one problem the tree alone does not solve. Insert only "cat", then ask search("ca"). Walking c then a succeeds — the node exists. But "ca" was never inserted, so the answer must be false.

The node exists because it lies on the way to "cat", not because "ca" is stored. Existing as a prefix and existing as a word are different facts, and the structure so far records only the first.

So each node carries a boolean: is this node the end of a word that was actually inserted? Then the two queries diverge at the last moment:

That single flag is the entire difference between the two operations, and forgetting it is the classic implementation bug — everything passes except the cases where one word is a prefix of another.

class TrieNode:
    def __init__(self):
        self.children = {}          # character -> TrieNode
        self.is_word = False        # does an inserted word END here?

class Trie:
    def __init__(self):
        self.root = TrieNode()      # the empty prefix; always exists

    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()    # create only what is missing
            node = node.children[ch]
        node.is_word = True                        # mark the endpoint

    def _walk(self, s):
        """Follow s from the root; return the node reached, or None."""
        node = self.root
        for ch in s:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

    def search(self, word):
        node = self._walk(word)
        return node is not None and node.is_word   # arrived AND it ends a word

    def starts_with(self, prefix):
        return self._walk(prefix) is not None      # merely arriving is enough

Factoring the shared walk into one helper makes the point visible in the code: the two queries are the same traversal with different acceptance conditions.

Costs. All three operations touch one node per query character, so each is O(L) where L is the query length — with no dependence on N, the number of stored words. Insertion allocates at most L new nodes, so total space is proportional to the number of characters inserted, which is at most N × L and considerably less when prefixes are shared.

Insert "cat", insert "car", then run three queries.

insert("cat"). The root has no c, so create one and step in. That node has no a, so create and step. No t, so create and step. Set is_word on the final node. Three nodes exist beyond the root, representing the prefixes "c", "ca" and "cat".

insert("car"). From the root, c exists — reuse it, create nothing. From "c", a exists — reuse. From "ca", there is no r, so create one node and step in. Set is_word. Only one node was added; the first two characters cost nothing because the structure already encoded them.

search("car"). Walk c, a, r. The final node has is_word set. Return true.

search("ca"). Walk c, a. The node exists, but it was created as part of building "cat" and no one ever inserted "ca", so its is_word is false. Return false. This is the case the flag exists for.

startsWith("ca"). Walk c, a. Arrived. Return true — two stored words do begin with "ca", and note the walk was character-for-character identical to the previous query.

startsWith("cab"). Walk c, a, then look for b under "ca". The children there are t and r only. Return false.

The gain is prefix operations in time proportional to the query rather than the dictionary. The cost is memory, and it is real: every node carries a container of children. With a fixed 26-slot array per node, a trie over a large sparse dictionary allocates enormous numbers of null pointers — a hash map per node uses less space but has a worse constant factor per lookup. Which to choose depends on how dense the alphabet usage is, and it is a good thing to raise unprompted.

Recognition signals for an unseen problem: autocomplete, prefix matching, "does any word start with", longest common prefix across many strings, spell-checking against a dictionary, word games on a board, IP routing tables. The common thread is many strings sharing structure, queried by their beginnings.

The two natural extensions both appear next. Store something other than a boolean at each node — a count of words passing through, or the word itself — and you can answer "how many words share this prefix" or collect every completion. Allow the query to branch rather than following one path, and you get wildcard matching, which is the Add and Search Words problem. Walk the trie in step with something else, such as a grid, and you get Word Search II.

Train the reflex: when a problem asks about the beginnings of many strings, do not store the strings. Store the paths, and let shared prefixes become shared structure.