Building the trie

For each word, start at the root and walk its letters. At every letter, if the current node has no child for it, create one. Then move into that child.

After the word's last letter, mark that node as an end. A dictionary of plain nested maps is enough: each node is a map from a letter to the next node.

Missing child? create it, then step into it.

After the last letter: mark the node as the end of this word.

In code

root = {}
for w in words:
    node = root
    for c in w:
        node = node.setdefault(c, {})
    node["#"] = True

words = [cat, car, dog] · • is the empty root

Insert "cat": walk from the root, creating c, a, t. Mark the last node: a word ends here.

Move 1 of 5

Searching the trie

To check whether the target is one of the inserted words, walk its letters the same way, but never create a node. If a letter is missing, the target was never inserted, like looking for a street that isn't on the map.

If every letter is found, the target exists only if the final node is marked as an end.

Missing letter: stop immediately and answer no.

All letters found: still check the end marker before saying yes.

In code

root = {}
for w in words:
    node = root
    for c in w:
        node = node.setdefault(c, {})
    node["#"] = True
node = root
for c in target:
    if c not in node:
        return False
    node = node[c]
return node.get("#", False)