940. Insert, Search, Starts With

Run q operations against a growing set of words, in the order given.

insert w add the word w to the set; this prints nothing search w print yes if w is in the set as a WHOLE WORD, else no starts w print yes if some word in the set BEGINS with w, else no

Inserting the same word twice changes nothing.

``` insert apple, search apple, search app, starts app, starts apq, search apple -> yes, no, yes, no, yes

insert cat, insert car, starts ca, search ca -> yes, no

insert dog, insert do, search do, search dog, search d, starts d -> yes, yes, no, yes ```

Read the second line carefully. ca is the beginning of two stored words and is not a stored word itself, so the two questions about the same string get opposite answers. That gap is the entire reason this problem exists.

## What most people reach for, and where it stops working

Keep the words in a hash set. search is then one lookup and is perfect. starts is the problem: a hash set is told nothing about prefixes, so the only way to answer is to test every word it holds.

With 10000 words stored and 10000 starts queries that is 10000 * 10000 = 10^8 word comparisons, each up to 20 characters, so 2 * 10^9 character comparisons. The set is not slow at what it does; it simply cannot answer the question.

## The structure

Store one node per distinct prefix. A node holds 26 child links, one per letter, each either the index of another node or -1, plus a flag saying whether a word ENDS here.

``` insert w: node = root for each letter c of w: if child[node][c] is absent: create a new node node = child[node][c] isEnd[node] = true

walk w: # shared by search and starts node = root for each letter c of w: if child[node][c] is absent: return "fell off" node = child[node][c] return node

search w: walk; no if it fell off, else isEnd[node] starts w: walk; no if it fell off, else yes ```

## Why the two queries differ by exactly one flag

Reaching a node means the walked string is a prefix of at least one stored word, because a node exists only when some insertion created it. So starts is answered by arriving at all. Being a stored WORD is a strictly stronger claim, and the flag is the only thing that records it. Without the flag there is no way to tell ca from cat, because both are just nodes.

## The boundary that breaks a careless walk

When a letter has no child, the walk must stop and report no immediately. The trap is code that breaks out of the loop but then reads isEnd[node] or prints yes from whatever node it happened to be standing on. On insert ab then search abc, that leaves you at the node for ab, whose flag is true, and you print yes for a word that was never inserted.

## Cost

Each operation costs the length of its word, at most 20 steps, so the whole stream is at most 20000 * 20 = 400000 steps regardless of how many words are stored. Space is at most 1 + 20000 * 20 = 400001 nodes.

## Against problem 936

936 builds the trie once and then asks HOW MANY words sit under a prefix. Here the set changes as the stream runs and the answers are yes or no, and the point is the difference between a prefix and a word, which a count hides.

Constraints - `1 ≤ q ≤ 20000` - Every `w` is 1 to 20 lowercase English letters. - At least one operation is a `search` or a `starts`.