Implement Magic Dictionary - Video Solutions

Problem Overview: Design a data structure that stores a dictionary of words and supports a search operation that returns true only if you can modify exactly one character of the input word to match a stored word. Exact matches are not allowed; the match must differ by exactly one position.

Approach 1: Brute-force Comparison (Build: O(n*m), Search: O(n*m), Space: O(n*m))

Store all dictionary words in a list or set. During search, iterate through every stored word and compare it with the query character by character. Count how many positions differ. If exactly one character differs, return true. If the difference is zero or more than one, continue checking other words.

This approach relies purely on direct string comparison and works because the constraint "exactly one modification" can be verified by scanning both strings simultaneously. The downside is that every query potentially scans the entire dictionary. With n words of length m, the search cost becomes O(n*m). It’s simple and acceptable for small dictionaries but scales poorly.

Approach 2: Hash Map for Character Patterns (Build: O(n*m), Search: O(m), Space: O(n*m))

Precompute wildcard patterns for each dictionary word. For every position in a word, replace that character with a placeholder such as *. For example, the word hello generates patterns like *ello, h*llo, he*lo, hel*o, and hell*. Store these patterns in a hash table that maps each pattern to the number of words that produce it.

During search, generate the same patterns for the query word and check if any pattern exists in the hash map. A matching pattern means there is a dictionary word differing by one character at that position. Additional checks ensure the match isn't the same word when only one dictionary entry produces the pattern.

The key insight is transforming the "one character difference" rule into shared wildcard patterns. Each lookup becomes a constant-time hash operation. Since only m patterns are generated for a word of length m, search runs in O(m) time after preprocessing. This approach heavily leverages string manipulation and efficient hash table lookups.

Recommended for interviews: The hash map pattern approach is what most interviewers expect. It shows you can convert a character-difference constraint into a pattern indexing problem and optimize lookups using hashing. Explaining the brute-force comparison first demonstrates clear reasoning about the problem, while the optimized design highlights strong data structure skills commonly tested in design-style questions.