Design a Word Dictionary with Wildcards

Question

Accepted Answer

To solve this efficiently, I propose using a Trie data structure. First, we define a Node class containing a map of children characters and a boolean flag indicating if a word ends there. When adding a word, we traverse the Trie, creating new nodes as needed, which takes linear time relative to the word length. The challenge lies in the search function with wildcards. For exact matches, we simply follow the path. However, when encountering a dot '.', we cannot determine the next character immediately. Instead, we use a recursive DFS approach. At any node where a dot appears, we iterate through all existing children keys. For each child, we recursively call the search function for the remaining substring. If any recursive call returns true, we immediately return true. If we reach the end of the query string and the current node marks a valid word end, we return true. Otherwise, we backtrack. This ensures we explore all potential paths without unnecessary computation. For example, searching for 'c.t' would check 'cat', 'cut', 'cot', etc., by branching at the second position. While worst-case time complexity increases with many wildcards, the average case remains efficient for sparse patterns. This approach aligns well with Uber's need for scalable, high-performance search features in their logistics platforms.

Design a Word Dictionary with Wildcards

Why Interviewers Ask This

How to Answer This Question

Key Points to Cover

Sample Answer

Common Mistakes to Avoid

Sound confident on this question in 5 minutes

Related Interview Questions

Convert Binary Tree to Doubly Linked List in Place

How do you implement a queue using two stacks?

Design a Set with $O(1)$ `insert`, `remove`, and `check`