Implement Trie for autocomplete — how do you handle wildcards (.)?

Question presented to candidate: "Design a word dictionary in Python with addWord(word) and search(pattern), where a . in the pattern matches any single letter. Then extend it to autocomplete: as the user types, return up to three suggestions in alphabetical order. What does a search cost when the pattern has many dots?"

What a strong answer should cover:

• A trie with an end-of-word flag; addWord is an O(L) insert.
• A recursive search with an index: one child for a letter, every child for a ., the end flag at the end, and an early return on the first match.
• Autocomplete as "walk the prefix, then a preorder DFS in letter order that stops after k words", which yields alphabetical results without sorting.
• Honest complexity: O(L) without dots, up to Σ^d paths with d dots (bounded by the trie size); a brute-force list scan is O(N·L) per query.
• Python details: dict children, any() over a generator (not a list) for the early exit, sorted() because dicts keep insertion order, and passing an index rather than slicing the pattern.

Clarifying questions expected:

• Does . match exactly one letter? Is there also a *?
• Should suggestions be alphabetical or ranked by popularity, and how many?
• Is the alphabet only lower-case a–z?

Code / implementation expected: Yes — a WordDictionary/trie class with addWord, search (with .) and a suggest(prefix, k) method, in Python.