Implement Trie

class TrieNode:
    def __init__(self):
        self.children = {}    # letter -> node
        self.is_end = False   # a word ends here

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def walk(self, s):
        node = self.root
        for ch in s:
            if ch not in node.children:
                return None   # dead end
            node = node.children[ch]
        return node

    def search(self, word):
        node = self.walk(word)
        return node is not None and node.is_end

    def startsWith(self, prefix):
        return self.walk(prefix) is not None

Implement Trie. It must insert words, search for a whole word, and check whether any word starts with a prefix.

Insert car, cart, cat and dog. Search car: true. Search C A: false, it's only a prefix. Starts with C A: true.

The simple way keeps a list and compares every word. With a hundred thousand words, each lookup scans them all.

A trie is a tree of letters. Each edge is one letter, and words with the same prefix share a path from the root. Each node holds a children map and an end flag, drawn as a gold flower.

Insert walks down from the root, adding a child for each missing letter, then flags the last node. Search walks the same way. A missing letter is a dead end: false. Otherwise, the last node must be flagged. Starts with skips that check.

Let's grow it. Car adds three nodes and a flower on R. Cart reuses C A R and adds T. Cat shares C A, then branches. Dog starts a new branch at the root. Search C A: the path exists, but A has no flower: false. Starts with C A is true. Search cart: four steps, ending on a flower: true. Search cow: no O under C. Dead end.

Each operation takes one step per letter: time depends on the word's length, not on how many words are stored. Space grows with the letters inserted.

Shared prefixes, one step per letter. That's Implement Trie.