#211

Medium

auto_awesomeString plus Depth-First Search

LeetCode Problem Workspace

Design Add and Search Words Data Structure

Build a WordDictionary supporting dynamic word addition and search with wildcard matching efficiently using Trie and DFS.

string depth first search design trie

Problem Statement

Design a data structure that allows adding words and searching whether a word or pattern exists. Patterns may include '.' which matches any single letter, requiring careful traversal of stored words.

Implement the WordDictionary class with the following methods: addWord(word) adds a word to the dictionary, and search(word) returns true if the exact word or a pattern matches any previously added word. Constraints include words up to 25 letters, lowercase letters, patterns with at most 2 dots, and up to 10^4 calls to addWord and search.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

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]

Explanation WordDictionary wordDictionary = new WordDictionary(); wordDictionary.addWord("bad"); wordDictionary.addWord("dad"); wordDictionary.addWord("mad"); wordDictionary.search("pad"); // return False wordDictionary.search("bad"); // return True wordDictionary.search(".ad"); // return True wordDictionary.search("b.."); // return True

Constraints

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

Solution Approach

Use a Trie for efficient prefix storage

Construct a Trie where each node represents a character. Adding a word inserts each character sequentially, marking the final node as an end of a word. This enables O(L) insertion, where L is word length, and supports efficient prefix traversal for searches.

DFS for pattern search with wildcards

When searching, use DFS to traverse the Trie. For normal letters, follow the corresponding child node. For '.', recursively explore all child nodes. Return true if a path matches the word length and ends at a marked word node.

Optimize with early pruning

Terminate DFS early when a path cannot possibly match the word or pattern. Skip branches if the remaining length exceeds possible Trie paths. This reduces unnecessary recursion, especially for patterns with multiple wildcards.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on word length L and Trie branching; addWord is O(L), search is O(26^k * L) in worst case with k wildcards. Space complexity is O(N*L) for storing N words, considering shared prefixes in Trie nodes.

What Interviewers Usually Probe

Look for efficient prefix storage and DFS handling of wildcards.
Check if you handle '.' correctly with recursive exploration.
Expect awareness of Trie node memory usage and early pruning for performance.

Common Pitfalls or Variants

Common pitfalls

Not handling '.' correctly can miss valid matches or overcount paths.
Failing to mark the end of words leads to false positives when searching prefixes.
Inefficient DFS without pruning may timeout with multiple wildcard searches.

Follow-up variants

Restrict to exact matches only, removing wildcard support.
Allow arbitrary number of wildcards instead of a max of 2.
Implement with a hash map of word lengths for faster lookup without Trie.

FAQ

What is the main strategy for the WordDictionary problem?

The main strategy is using a Trie to store words efficiently and DFS to handle search patterns including '.' wildcards.

How do I handle '.' in searches for this problem?

During DFS traversal, treat '.' as a wildcard and explore all child nodes recursively to match any character at that position.

Why is a Trie preferred over a list for this problem?

A Trie allows prefix sharing and O(L) insertions and searches, while a list would require checking every word for matches, which is slower for large datasets.

Can this approach handle multiple '.' wildcards efficiently?

Yes, but each wildcard increases branching in DFS exponentially. Limiting the number of wildcards and pruning invalid paths keeps searches efficient.

Is this problem mainly String plus Depth-First Search pattern?

Yes, it combines string manipulation and DFS traversal over a Trie structure to support pattern matching efficiently.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

class Trie:
    def __init__(self):
        self.children = [None] * 26
        self.is_end = False


class WordDictionary:
    def __init__(self):
        self.trie = Trie()

    def addWord(self, word: str) -> None:
        node = self.trie
        for c in word:
            idx = ord(c) - ord('a')
            if node.children[idx] is None:
                node.children[idx] = Trie()
            node = node.children[idx]
        node.is_end = True

    def search(self, word: str) -> bool:
        def search(word, node):
            for i in range(len(word)):
                c = word[i]
                idx = ord(c) - ord('a')
                if c != '.' and node.children[idx] is None:
                    return False
                if c == '.':
                    for child in node.children:
                        if child is not None and search(word[i + 1 :], child):
                            return True
                    return False
                node = node.children[idx]
            return node.is_end

        return search(word, self.trie)


# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)

Continue Practicing

#676 implement magic dictionary #208 implement trie prefix tree #297 serialize and deserialize binary tree