Tries

A trie, pronounced "try", is a tree where each edge is a character. Words that share a prefix share the path from the root. The words cat and car share the edges for c and a, then split into t and r.

Each node holds its children, keyed by character, and a flag that is true when some inserted word ends on that node. A missing child means that continuation has never been inserted. Insert walks the characters, creating a child when it is missing, and marks the last node as a word. Search walks the same path and checks the flag. Ending on a node is not enough: a prefix of a stored word is not itself a word unless the flag says so. Both walks are proportional to the length of the word, not to how many other words you stored.

A hash set of whole words is also fast on average and is shorter to write. Exact lookup alone does not force a trie, and a set would pass a test that only asks "is this word present?". The trie earns its place when you care about prefixes. "Which words start with ca?" is a walk to that node, then a small traversal of whatever sits underneath. Build the trie when the point of the exercise is to leave with one more structure you can draw.