Implement Trie (Prefix Tree)

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

A hash set finds whole words in O(L) but cannot answer a prefix question without scanning every word. Storing every prefix in a second set costs 210 letters for a single 20-letter word. A trie stores each shared prefix once and answers both questions with one walk.

MediumTrie

+10

Build a trie (prefix tree) 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.

Operation i is ops[i] on words[i]. Run them in order on an empty trie and return one string each: "null" for an insert, "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: car begins card, so startsWith car is "true", but car was never inserted, so the first search is "false". After insert car 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 but neither is exactly te, so startsWith is "true" and search is "false". No word begins with tex, and tea is a prefix of itself.

Input: ops = ["search", "startsWith", "insert", "search", "startsWith", "startsWith"]words = ["dog", "d", "dog", "dog", "dogs", "do"]
Output: ["false", "false", "null", "true", "false", "true"]
Explanation: On the empty trie both queries are "false". After insert dog, the search finds it, no word begins with dogs, and do begins dog.

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, but it has no notion of beginnings, so startsWith would scan every word. A trie stores each word as a path of letters from the root: words that start alike share a path, and a flag marks where a stored word ends. Both queries become one walk of at most L links.

Keep a list of words and scan it

Intuition

Keep every inserted word in a list. search w compares w with each stored word, and startsWith p checks whether any stored word begins with p. It is correct because it tests the definition directly. With n stored words, each query costs up to n comparisons of up to L letters: 1,000 words and 1,000 queries make a million string comparisons.

Algorithm

Start with an empty list.
insert w: append w.
search w: return whether some stored word equals w.
startsWith p: return whether some stored word begins with p.

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 stands for one prefix, the letters on the path from the root to it. It holds a child link for each letter that can come next (26 slots or a map) and a flag isEnd that says whether a stored word ends exactly there. Inserting tea creates the nodes for t, te and tea; inserting ten then adds only ten, because the two words share the path for te.

A walk that meets a missing link proves no stored word begins with those letters: tex stops at te, which has no x link. A walk that reaches the end stands on the node for the query, so startsWith is true and search answers with the flag. The node for te exists but its flag is off, so search te is false. Each operation follows at most L links however many words are stored, and the trie holds one node per distinct prefix.

Algorithm

Create a root with no child links and isEnd off.
insert w: from the root, follow the link for each letter, creating the node when it is missing. Set isEnd on the last node.
find(p): from the root, follow the link for each letter; return nothing as soon as one is missing, else the node reached.
search w: true when find(w) returns a node with isEnd set.
startsWith p: true when find(p) returns a node.

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

Letting search answer true whenever the path exists. After insert card, the path for car exists, but search car must be false.
Setting isEnd only on newly created nodes. Inserting card after cards creates nothing, yet the last node needs its flag.
Creating a fresh child when the link already exists. Inserting ten with a new t node loses tea.
Reading past the end of the path. startsWith sunny with only sun stored must stop at the first missing link and answer false.

Frequently asked questions3

What is the time complexity of a trie?

Insert, search and startsWith each follow one link per letter, so each takes O(L) for a word of length L, however many words are stored. The space is O(T) nodes for T inserted letters in total, each node holding up to 26 child links.

Why use a trie instead of a hash set?

A hash set finds whole words in O(L) but cannot answer a prefix question without scanning every word. Storing every prefix in a second set costs 210 letters for a single 20-letter word. A trie stores each shared prefix once and answers both questions with one walk.

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

An array finds a child with one index but costs 26 slots per node, even for a node with one child. A map stores only the children that exist and works for any alphabet, at the cost of a hash per letter. For lowercase English either works; for Unicode or sparse tries a map saves memory.

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

Test #1

Test #2

Test #3

Arguments

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

Expected Output

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