Implement Trie Prefix Tree

Just keep every inserted word in a list (or set). insert is trivial. search checks for an exact match; startsWith checks whether any stored word starts with the given prefix — both require scanning the whole collection in the worst case.

class Trie:
    def __init__(self):
        self.words = []

    def insert(self, word: str) -> None:
        self.words.append(word)

    def search(self, word: str) -> bool:
        return word in self.words

    def startsWith(self, prefix: str) -> bool:
        return any(w.startswith(prefix) for w in self.words)

Correct, but search on a plain list is O(n·L) (n words, each comparison up to length L), and startsWith is worse since it cannot stop early — every stored word must be checked. With up to 3·10^4 calls this is far too slow to be the intended solution; it exists here mainly to highlight what the trie buys us.

Build an explicit tree: each node holds a map from character to child node, plus a flag for “a word ends here.” insert walks the word, creating any missing nodes along the way, then flags the final node. search/startsWith both walk the same way and just differ in what they check once the walk finishes: search requires the end-of-word flag, startsWith only requires the path to exist.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False

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

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_word = True

    def search(self, word: str) -> bool:
        node = self._find(word)
        return node is not None and node.is_word

    def startsWith(self, prefix: str) -> bool:
        return self._find(prefix) is not None

    def _find(self, s: str):
        node = self.root
        for ch in s:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

Watch where each operation stops on the path and whether the final node carries the end marker — that single flag is the only difference between a search hit and a startsWith hit:

Complexity: every operation walks exactly one character per level, so each is O(L) where L is the length of the word or prefix — independent of how many words are stored. Space is bounded by the total number of distinct characters across all inserted prefixes, since shared prefixes only cost one set of nodes.