Difficulty: MediumTries

Design Add and Search Words Data Structure

Problem in Plain English

Design a word dictionary that stores every added word and reports whether a query matches any stored word, where a dot in the query stands for any single letter. Adding is exact, while searching must handle wildcards.

Problem Statement

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class with void addWord(word), which stores word for later matching, and bool search(word), which returns true if some stored word matches the query. The query may contain dots ., where each dot matches any single lowercase English letter.

Constraints

1 <= word.length <= 25
word in addWord consists of lowercase English letters.
word in search consists of . or lowercase English letters.
There will be at most 2 dots in word for search queries.
At most 10^4 calls will be made to addWord and search.

Examples

Example 1

Input: ["WordDictionary","addWord","addWord","addWord","search","search","search","search"] [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output: [null,null,null,null,false,true,true,true]

After storing bad, dad and mad, pad matches nothing, bad matches exactly, .ad matches all three, and b.. matches bad.

Example 2

Input: ["WordDictionary","search","addWord","addWord","search","search"] [[],["."],["a"],["a"],["."],["aa"]]
Output: [null,false,null,null,true,false]

The empty dictionary matches nothing. Adding a twice does not change existence semantics: . matches the one-letter word, while aa needs two letters.

Example 3

Input: ["WordDictionary","addWord","addWord","search","search","search","search","search"] [[],["ab"],["acd"],[".."],["a."],[".c"],["ac"],["ac."]]
Output: [null,null,null,true,true,false,false,true]

.. and a. match ab. Neither .c nor ac is a complete added word: ac is only a prefix of acd. In ac., the dot consumes the final d, so it matches acd.

Intuition

A dot consumes exactly one character, so a query can only match a complete stored word of the same length. In Example 1, .ad can use the first letter of bad, dad, or mad. Length buckets compare whole candidates; a trie shares prefixes and explores alternative children only at dots. Reaching a prefix is insufficient unless that node marks the end of an added word.

Approaches

Group by Length

Solution Details

Reveal Group by Length: intuition, complexity, and code

Intuition

A query can only match stored words of the same length, so bucketing words by length shrinks every search to one bucket. Each candidate is then checked letter by letter with dots accepted as automatic matches.

Step-by-Step Logic

Initialize empty length buckets. Add bad, dad, and mad to the length-3 list in that order.
For pad, examine all three candidates. Each fails at index 0: p differs from b, d, and m; return false.
For bad, candidate bad passes indices 0, 1, and 2; return true without checking later candidates.
For .ad, candidate bad accepts b at the dot, then matches a and d; return true.
For b.., candidate bad matches b and accepts a and d at the two dots; return true.

Why It Works

Any matching word must have the same length because each query position consumes one letter, including a dot. Therefore the selected bucket contains every possible match and excludes only impossible lengths. For a candidate, the loop rejects exactly when an exact query letter differs at some position; a dot imposes no letter restriction. A candidate surviving all positions is a full match, and rejecting every candidate proves no stored word matches. Duplicate candidates cannot change this existence result.

Dry Run

Group by Length: variable states at each step
operation / candidate	index	comparison	bucket / transition
constructor	none	none	buckets empty; output null
add bad	none	none	length 3 becomes `[bad]`; null
add dad	none	none	length 3 becomes `[bad,dad]`; null
add mad	none	none	length 3 becomes `[bad,dad,mad]`; null
pad / bad	0	p differs from b	reject candidate
pad / dad	0	p differs from d	reject candidate
pad / mad	0	p differs from m	bucket exhausted; false
bad / bad	0	b equals b	continue to 1
bad / bad	1	a equals a	continue to 2
bad / bad	2	d equals d	all 3 positions passed; true
.ad / bad	0	dot accepts b	continue to 1
.ad / bad	1	a equals a	continue to 2
.ad / bad	2	d equals d	all positions passed; true
b.. / bad	0	b equals b	continue to 1
b.. / bad	1	dot accepts a	continue to 2
b.. / bad	2	dot accepts d	all positions passed; true
complete sequence	none	none	`[null,null,null,null,false,true,true,true]`

Complexity Analysis

Time Complexity

O(km)

Space Complexity

O(T)

For a search, m is query length and k is the larger of 1 and the number of stored entries in its length bucket; at most km character comparisons plus constant lookup work are needed, including an empty bucket. addWord stores an existing immutable string reference in amortized O(1) time. Across N additions with T total characters, retaining strings and O(N) list references takes O(T) space since each word is nonempty; containers alone use O(N), search uses O(1) extra space. Duplicate additions occupy list slots even though they do not change the answer.

Code

Solution.java

1import java.util.ArrayList;2import java.util.HashMap;3import java.util.List;4import java.util.Map;5
6class WordDictionary {7    private Map<Integer, List<String>> buckets;8
9    public WordDictionary() {10        buckets = new HashMap<>();11    }12
13    public void addWord(String word) {14        buckets.computeIfAbsent(word.length(), k -> new ArrayList<>()).add(word);15    }16
17    public boolean search(String word) {18        List<String> group = buckets.get(word.length());19        if (group == null) {20            return false;21        }22        for (String candidate : group) {23            boolean match = true;24            // A dot consumes one position; exact letters must agree.25            for (int i = 0; i < word.length(); i++) {26                if (word.charAt(i) != '.' && word.charAt(i) != candidate.charAt(i)) {27                    match = false;28                    break;29                }30            }31            if (match) {32                return true;33            }34        }35        return false;36    }37}

Hints

Hint 1

A dot matches one letter, so first discard stored words whose length differs from the query.

Hint 2

Shared prefixes can be stored once in a trie; an exact letter follows one child.

Hint 3

At a dot, try every existing child and succeed if any continuation succeeds. Accept at the end only when the node is marked as a word end.

Edge Cases

Search before any insertion returns false, including a dot query.
Duplicate additions preserve existence; a list bucket can retain repeated references while a trie reuses the same path.
An inserted prefix such as a and a longer word such as ab each need their own terminal marker.
A prefix such as ac of acd is not automatically a word.
A query with two dots can branch at both positions, but every branch must consume exactly the query length.
Length 25 and 10000 total calls are legal; at most two query positions are dots.

Common Mistakes and Interview Tips

Accepting a trie node when the query ends without checking its word-end flag accepts unadded prefixes.
Treating a dot like a star that consumes zero or many letters changes the matching rule.
Returning false after the first failed wildcard branch instead of trying its siblings loses valid matches.
Failing to advance the query index for a wildcard consumes the wrong number of letters.
Claiming trie searches always take linear time ignores wildcard branching; the bound depends on the number of dots.

Key Takeaway

When prefix storage meets wildcard queries, keep the words in a trie and let depth-first search fan out only where the query actually branches.