Design Add and Search Words Data Structure - Video Solutions

Problem Overview: Build a data structure that supports two operations: addWord(word) to store a word and search(pattern) to check if any stored word matches the pattern. The search pattern may include the wildcard ., which matches any single character.

Approach 1: HashMap with DFS for Wildcards (Time: add O(m), search O(n * 26^w), Space: O(n*m))

Store words grouped by length using a HashMap<length, List<word>>. During search, only compare words of the same length as the query. Iterate through each candidate word and check character-by-character, treating . as a match for any character. This approach avoids scanning irrelevant lengths but still requires scanning many candidates when the dictionary grows. It works well for small datasets but degrades when many words share the same length.

Approach 2: Backtracking with Pattern Matching (Time: worst case O(26^w * m), Space: O(m) recursion)

During search, recursively explore possible character matches whenever a . appears. Each wildcard branches into multiple possibilities, effectively performing backtracking over possible character substitutions. This technique demonstrates how wildcard matching works conceptually, but without a specialized structure it repeatedly scans strings and becomes inefficient as the dataset grows. It mainly serves as an intermediate idea before introducing a trie.

Approach 3: Trie Data Structure with DFS (Time: add O(m), search average O(m), worst O(26^w * m), Space: O(n*m))

Insert each word into a Trie, where each node represents a character. addWord simply iterates through characters and creates nodes if missing. For search, traverse the trie normally until encountering .. When a wildcard appears, run a DFS across all child nodes and continue matching the remaining characters. This structure drastically prunes the search space because only valid prefixes are explored. The trie efficiently supports prefix traversal and wildcard branching while keeping operations proportional to the word length.

Recommended for interviews: The trie-based solution is what interviewers expect. It shows you understand prefix trees, branching search with DFS, and how to optimize wildcard pattern matching. Mentioning the naive length-bucket scan demonstrates baseline reasoning, but implementing the trie shows strong command of string indexing and data structure design.