Design Add and Search Words Data Structure

Explanation & Solution

Description

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

Implement the WordDictionary class:

WordDictionary() — Initializes the object.
addWord(word) — Adds word to the data structure. It can be matched later.
search(word) — Returns true if there is any string in the data structure that matches word, or false otherwise. word may contain dots '.' where dots can be matched with any letter.

Input:operations = ["WordDictionary","addWord","addWord","addWord","search","search","search","search"], operands = [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]

WordDictionary

addWord

Output:[null,null,null,null,false,true,true,true]

null

false

true

Explanation: The WordDictionary is initialized, then "bad", "dad", and "mad" are added. Searching for "pad" returns false (not added). Searching for "bad" returns true (exact match). Searching for ".ad" returns true (matches "bad", "dad", or "mad"). Searching for "b.." returns true (matches "bad").

Constraints

1 <= word.length <= 25
word in addWord consists of lowercase English letters
word in search consists of lowercase English letters or '.'
At most 10⁴ calls will be made to addWord and search

Approach

Trie pattern

1. Trie Node Structure

Each node has a children object mapping characters to child nodes
Each node has an isEnd boolean to mark the end of a complete word
The WordDictionary itself acts as the root node

2. Adding a Word

Start at the root and traverse character by character
If the character does not exist in the current node's children, create a new node
Move to the child node for each character
Mark the final node as isEnd = true

3. Searching with Wildcards

Use DFS (depth-first search) to handle the '.' wildcard
If the current character is '.', try every child node recursively
If any child path leads to a match, return true
If the current character is a regular letter, follow that specific child

4. Base Case

When we reach the end of the search word (index === word.length), check if the current node's isEnd is true
This ensures we only match complete words, not just prefixes

Key Insight

The '.' wildcard transforms a simple trie lookup into a DFS problem — when we encounter a dot, we branch out and explore all possible children
Without wildcards, search is O(m). With wildcards, the worst case is O(26^m) but in practice the trie structure prunes most branches

Time

O(m) for `addWord`, **O(26^m)** worst case for `search` with wildcards

Space

O(n * m) where n is the number of words and m is the average word length

Solution Code

Implement Trie (Prefix Tree)

Word Search II