196. Implement a Trie - Insert and Search Words

Build a trie from n given words, then answer q queries; each query is a word, and you print 'Yes' if it was one of the originally inserted words, otherwise 'No'. Print all q answers space-separated on one line.

Input: The first line contains an integer n, followed by n lines each with a word to insert. The next line contains an integer q, followed by q lines each with a query word. Output: Print q answers space-separated on one line, each 'Yes' if that query word was one of the originally inserted words, otherwise 'No'.

1 <= n, q <= 10^5

Every OTHER Trie problem on this platform builds directly on this exact insert/search foundation - master this one first, since the harder trie problems just add extra bookkeeping (counts, sorting, XOR) on top of this same walking pattern.

Imagine building a tree made entirely out of letters, where following a path from the root spells out a word one letter at a time. This problem asks you to build exactly that tree from a list of words, then check whether other words exist somewhere in it. Brute force: Store all inserted words in a plain list or hash set, and for each query just check set membership directly - this actually works fine and is O(1) average per query with a hash set, but doesn't scale as elegantly to prefix-based operations (like the other problems in this category) the way a trie naturally does. Optimised: A trie shares memory across words with common prefixes (all words starting with 'app' share the same first three nodes), and crucially, it's the natural data structure for ANY prefix-related question (not just exact-match lookups) - which is exactly why this category builds up from here into autocomplete, unique-prefix, and substring-counting problems that a plain hash set can't elegantly answer.

Store the n inserted words in a plain list, and for each of the q queries, compare the query word against every stored word directly for exact equality until a match is found or the list is exhausted. This is correct since direct string comparison correctly determines membership, but every query costs time proportional to both the number of stored words and their lengths, since in the worst case it must check them all. Time: O(n * q * L) Space: O(n * L)

Build a trie (prefix tree) by inserting each of the n words character by character, marking the final node of each inserted word as a word-end; then answer each query by walking the trie one character at a time and reporting 'Yes' only if the walk completes and lands on a marked word-end node. This is correct because a trie encodes the exact set of inserted words along their character paths, and it is preferable to a hash set because words sharing a common prefix share the same trie nodes, giving compact storage and lookup time that depends only on the query's own length rather than on hash quality or collisions, with worst-case guarantees that don't degrade. Time: O((n + q) * L) Space: O(sum of word lengths)

Insert all n words into a hash set, then answer each query by hashing the query word and checking set membership in expected constant time relative to the number of stored words. This is correct because a hash set guarantees an exact match check, and it is faster than the brute-force scan because lookup no longer depends on how many words were previously inserted, only on the length of the word being hashed, though performance can degrade with hash collisions and it doesn't exploit any shared structure between similar words. Time: O((n + q) * L) Space: O(n * L)

1. Start at an empty root node representing 'no letters typed yet'. 2. For each word being inserted, walk character by character, creating a new child node for any letter that doesn't already have a branch, and moving into the existing branch if it does. 3. Mark the final node of each inserted word with a special 'end of word' flag. 4. To search a word, walk the exact same way - if you ever hit a letter with no matching branch, the word doesn't exist; if you successfully walk the whole word, the answer depends on whether the FINAL node's 'end of word' flag is actually set.

Time: Both insertion and search take time proportional to the LENGTH of the word being processed, completely independent of how many other words are already in the trie. Space: Proportional to the total number of characters across all inserted words in the worst case (no shared prefixes) - but in practice, shared prefixes mean real-world tries often use meaningfully less space than storing every word separately.

Test a query that is a strict prefix of an inserted word but was never itself inserted (must print 'No'), a query identical to an inserted word, and n, q up to 10^5 for performance.

Be ready to explain clearly why a node being 'reachable' isn't the same as it being a 'complete word' - this exact end-of-word-flag distinction is the single most common mistake in a live trie implementation.