Implement Trie (Prefix Tree)

Q: Why use a trie instead of a hash set?

A hash set answers whole-word lookups in O(L) , but it cannot answer a prefix question without scanning every word. You could add a second set holding every prefix of every word, but a 20-letter word then stores 20 prefixes with 210 letters between them. A trie stores each shared prefix once and answers both questions with the same walk. With 26 array slots per node, a walk below a prefix also meets the words in letter order, which autocomplete needs.

MediumTrie

+10

A trie, or prefix tree, stores words so that questions about their beginnings are fast. Build one for lowercase words with three operations: insert w adds the word w, search w tells whether w itself was inserted, and startsWith p tells whether some inserted word begins with p. A word counts as a prefix of itself.

You get the operations in order as ops, and words[i] is the word or prefix for ops[i]. Run them on one trie that starts empty and return one string per operation: "null" for an insert, and "true" or "false" for a search or a startsWith.

Function

trieOps(ops: string-array, words: string-array) → string-array

opsstring-array: the operations, in the order they run
wordsstring-array: the word or prefix for each operation
Returnsstring-array: one answer per operation, as text

Constraints

1 ≤ ops.length ≤ 2000
words.length == ops.length
Every ops[i] is insert, search or startsWith.
1 ≤ words[i].length ≤ 20
words[i] holds only lowercase English letters.

Examples

Input: ops = ["insert", "search", "startsWith", "insert", "search"]words = ["card", "car", "car", "car", "car"]
Output: ["null", "false", "true", "null", "true"]
Explanation: Only card is stored at first, so searching for car returns "false": it was never inserted as a word. It is the beginning of card, so startsWith car returns "true". Once car is inserted, the search finds it.

Input: ops = ["insert", "insert", "startsWith", "search", "startsWith", "search", "startsWith"]words = ["tea", "ten", "te", "te", "tex", "ten", "tea"]
Output: ["null", "null", "true", "false", "false", "true", "true"]
Explanation: Both words begin with te, so startsWith te is "true", but no word is exactly te, so the search fails. No word begins with tex. ten was inserted, and tea is a prefix of itself, so the last two answers are "true".

Input: ops = ["search", "startsWith", "insert", "search", "startsWith", "startsWith"]words = ["dog", "d", "dog", "dog", "dogs", "do"]
Output: ["false", "false", "null", "true", "false", "true"]
Explanation: The trie starts empty, so the first two answers are "false". After dog is inserted, the search finds it, no word begins with dogs, and do begins dog.

+16 hidden tests on Submit

Follow-up

How would you add a countPrefix p operation that returns how many distinct stored words begin with p, still in O(L) time?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

A hash set answers search at once, but startsWith asks about every word that begins a certain way, and a set has no notion of beginnings. A trie stores the beginnings themselves: every word is a path of letters from the root, words that start alike share the start of their path, and a flag on a node marks where a stored word ends. Both questions then take one walk of at most L links, where L is the length of the query, however many words are stored.

Keep a list of words and scan it

Intuition

Keep every inserted word in a list. For search w, compare w with each stored word. For startsWith p, check whether any stored word begins with p. In the second example, startsWith te looks at tea first and stops there; startsWith tex has to look at both words before it answers "false".

This is correct, and with the limits here it finishes, but every query pays for every stored word. With n words stored, a query costs up to n comparisons of up to L letters each. 1,000 stored words and 1,000 queries make a million string comparisons, and the work keeps growing with the dictionary. Nothing is shared either: tea and ten each store their own t and e.

Algorithm

Start with an empty list of words.
For insert w: append w to the list.
For search w: return whether some stored word equals w.
For startsWith p: return whether some stored word begins with p.
Record each answer as text and return the list.

def trieOps(ops, words):
    stored = []
    result = []
    for op, word in zip(ops, words):
        if op == "insert":
            stored.append(word)
            result.append("null")
        elif op == "search":
            found = any(s == word for s in stored)
            result.append("true" if found else "false")
        else:
            found = any(s.startswith(word) for s in stored)
            result.append("true" if found else "false")
    return result

A trie: child links and an end flag

Intuition

Each node of a trie stands for one prefix: the letters on the path from the root down to it. The root stands for the empty prefix. A node holds two things: a child link for each letter that can come next (an array of 26 slots, or a map from letter to node) and a flag, isEnd, that says whether a stored word ends exactly at this node.

insert walks the word from the root. For each letter it follows the child link, creating the node first if the link is missing, and at the last letter it sets isEnd. In the second example, inserting tea creates the nodes for t, te and tea and marks tea. Inserting ten reuses t and te and adds only ten. The two words share the path for te, which is where the name prefix tree comes from.

search and startsWith make the same walk without creating anything. If a link is missing, no stored word begins with those letters, so both answer false: tex stops at the node for te, which has no x link. If the walk reaches the end, the node it stands on is the prefix you asked about. startsWith answers true, and search answers with that node's flag. The node for te exists, but its flag is off, because the words that pass through it end lower down. So startsWith te is true and search te is false.

The flag is what separates a word from a prefix. In the first example, after card is inserted the path c, a, r exists. Without the flag, search car would wrongly answer true. Inserting car later creates no node at all; it only switches the flag on.

Each operation follows at most L links, where L is the length of its word, so it costs O(L) no matter how many words are stored. The trie holds one node per distinct prefix, never more than the total number of letters inserted.

Algorithm

Define a node with child links (26 slots or a map) and an isEnd flag, and create an empty root.
For insert w: from the root, follow the link for each letter of w, creating the node when the link is missing. Set isEnd on the last node.
Write a helper find(p): from the root, follow the link for each letter of p, and give up as soon as one is missing. Return the node reached.
For search w: answer true when find(w) reaches a node whose isEnd is set.
For startsWith p: answer true when find(p) reaches a node.
Run the operations in order and record "null", "true" or "false" for each.

class TrieNode:
    def __init__(self):
        self.children = {}   # letter -> TrieNode
        self.is_end = False  # does a stored word end at this node?


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def _find(self, prefix):
        # Follow the letters from the root; None as soon as a link is missing.
        node = self.root
        for ch in prefix:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

    def search(self, word):
        node = self._find(word)
        return node is not None and node.is_end

    def starts_with(self, prefix):
        return self._find(prefix) is not None


def trieOps(ops, words):
    trie = Trie()
    result = []
    for op, word in zip(ops, words):
        if op == "insert":
            trie.insert(word)
            result.append("null")
        elif op == "search":
            result.append("true" if trie.search(word) else "false")
        else:
            result.append("true" if trie.starts_with(word) else "false")
    return result

Pitfalls and edge cases

Most bugs come from mixing up "a word ends here" with "a word passes through here".

Letting search answer true whenever the path exists. After inserting card, the path for car exists, but car was never inserted.
Setting isEnd only on newly created nodes. Inserting card after cards creates nothing, yet the last node still needs its flag.
Creating a fresh child even when the link exists. That cuts off everything stored below it: inserting ten with a new t node loses tea.
Forgetting that a word is a prefix of itself. After inserting tea, startsWith tea is true.
Reading past the end of the path. A prefix longer than every word, like sunny when only sun is stored, must stop at the first missing link and answer false.
Returning booleans or leaving inserts out of the answer. Every operation gets one string, including "null" for an insert.

Frequently asked questions4

What is the time complexity of a trie?

Insert, search and startsWith each follow one link per letter of their argument, so each takes O(L) time for a word of length L, independent of how many words are stored. The trie holds at most one node per inserted letter, so the space is O(T) nodes for T inserted letters in total, and each node stores up to 26 child links.

Why use a trie instead of a hash set?

A hash set answers whole-word lookups in O(L), but it cannot answer a prefix question without scanning every word. You could add a second set holding every prefix of every word, but a 20-letter word then stores 20 prefixes with 210 letters between them. A trie stores each shared prefix once and answers both questions with the same walk. With 26 array slots per node, a walk below a prefix also meets the words in letter order, which autocomplete needs.

Should a trie node use an array of 26 links or a hash map?

An array gives the fastest child lookup, one index per letter, but every node pays for 26 slots even when it uses one. A map stores only the children that exist and works for any alphabet, at the cost of a hashing step per letter. For lowercase English words either is fine; for Unicode text or sparse tries, a map saves a lot of memory.

Where are tries used in practice?

Autocomplete and search suggestions walk a trie to the typed prefix and list the words below it. Spell checkers, word games that search a board for dictionary words, and routers that find the longest matching address prefix use the same structure. Any time many strings share beginnings and you query by beginning, a trie fits.

Python

def trieOps(ops, words):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

ops = ["insert", "search", "startsWith", "insert", "search"]
words = ["card", "car", "car", "car", "car"]

Expected

["null", "false", "true", "null", "true"]