Implement Trie (Prefix Tree)

Implement a trie with insert(word), search(word) (exact match), and startsWith(prefix) (any word begins with this prefix).

Example

Insert apple. search("apple") → true. search("app") → false (never inserted as a complete word). startsWith("app") → true (it's a prefix of apple).

Approach

Each trie node holds a map from character to child node, plus an is_end flag marking "a complete word ends here." Inserting a word walks/creates one node per character and flips is_end on the last one. search and startsWith both walk the same path — the only difference is search additionally requires is_end to be true at the final node, while startsWith only requires the path to exist. All three operations are O(word length), independent of how many words are stored.

Walkthrough

Inserting app then apple, then running three queries:

1class TrieNode:
2    def __init__(self):
3        self.children = {}
4        self.is_end = False
5
6class Trie:
7    def __init__(self):
8        self.root = TrieNode()
9
10    def insert(self, word):
11        node = self.root
12        for c in word:
13            if c not in node.children:
14                node.children[c] = TrieNode()
15            node = node.children[c]
16        node.is_end = True
17
18    def search(self, word):
19        node = self._find(word)
20        return node is not None and node.is_end
21
22    def starts_with(self, prefix):
23        return self._find(prefix) is not None

Input format

Line 1: words to insert, space-separated Line 2: number of queries q Next q lines: search <word> or startsWith <prefix>

Print each query's result (true/false), space-separated.