Look up words where '.' stands for any letter

Store the words in a trie with an end marker. A query walks the trie letter by letter; at a '.', try every child. Plain letters cost O(1) per step; each '.' can branch, so the worst case is the number of trie nodes, but typical queries are fast. Building is O(total letters). With T total letters and q ≥ 1 queries the worst case is O(q · T) time, and the trie takes O(T) space.

The trie plus DFS on wildcards is the template for pattern lookups.

Grouping words by length first cuts the search, since a match must have the same length.

A regex over every stored word is O(words × length) per query.

class Node:
    def __init__(self) -> None:
        self.kids: dict[str, Node] = {}
        self.ends = False  # a stored word stops here


def wildcard_hits(words: list[str], queries: list[str]) -> list[bool]:
    root = Node()
    for w in words:
        node = root
        for ch in w:
            node = node.kids.setdefault(ch, Node())
        node.ends = True

    def fits(node: Node, q: str, i: int) -> bool:
        if i == len(q):
            return node.ends
        if q[i] != ".":
            step = node.kids.get(q[i])
            return step is not None and fits(step, q, i + 1)
        return any(fits(kid, q, i + 1) for kid in node.kids.values())

    return [fits(root, q, 0) for q in queries]

Common mistakes

• Forgetting the end marker, so 'ca' matches because 'cat' is stored.
• Returning on the first branch that fails instead of trying the others.

Mention the end marker; it is the classic bug here.

Follow-up questions

Think of your answer first, then open the hint.

1. How do you support '*' (any run of letters)?

   Show hint

   At '*', either skip it or consume one letter and stay on '*': a DFS with two branches.

2. How would you handle a huge word list?

   Show hint

   Bucket by length, and build one trie per length.