Design Add and Search Words Data Structure

LeetCode 211: Design Add and Search Words Data Structure Solution & Explanation

Problem Overview

TL;DR: We implement a Trie (Prefix Tree) where the search operation utilizes Depth-First Search (DFS) to handle wildcard characters by exploring all potential child nodes at the wildcard's level.

The problem asks us to design a data structure that can store a dynamic set of strings and perform search queries. The unique challenge in LeetCode 211 is that the search query may contain the . character, which functions as a wildcard matching any single letter. While standard exact matching is trivial with a hash set, the wildcard requirement necessitates a structure that supports efficient prefix traversal and branching, making "Design Add and Search Words Data Structure" a classic application of tree-based string structures.

Brute Force Approach for Design Add and Search Words Data Structure

A naive approach would utilize a simple list or dynamic array to store every word added via addWord.

When search(word) is called:

1. Iterate through every string stored in the list.
2. If the length of the stored string differs from the query word, skip it.
3. If lengths match, iterate character by character.
   • If the query character is . or matches the stored character, continue.
   • If there is a mismatch, stop checking this stored string.
4. If the loop completes for any stored string without mismatches, return true.

Why this fails: While this might pass on small datasets, the time complexity for search is $O(M \cdot L)$, where $M$ is the total number of added words and $L$ is the length of the word. If we add thousands of words and perform thousands of searches, the total runtime approaches $O(N \cdot M \cdot L)$. This linear scan is inefficient because it repeatedly compares prefixes of words that share common starting characters (e.g., checking "apple", "apply", and "append" separately).

Algorithm Strategy: Design Patterns (Trie)

We will implement a TrieNode class and a WordDictionary class.

The Data Structure:

• TrieNode: Contains an array of size 26 (for lowercase English letters) representing links to children nodes. It also contains a boolean flag isEnd to indicate if a word concludes at this node.
• Root: The WordDictionary holds a single root TrieNode.

The Operations:

1. addWord(word):

   • Start at the root.
   • For each character in word, calculate the index ($0-25$).
   • If the child pointer at that index is null, create a new TrieNode.
   • Move the current pointer to the child.
   • After the loop, set isEnd to true on the final node.

2. search(word):

   • This requires a helper function match(node, index) to support recursion.
   • Base Case: If index equals the length of word, we have processed the entire query. Return node.isEnd.
   • Recursive Step: Get the character at word[index].
     • Case 1 (Literal): If the character is a letter, check if the corresponding child node exists. If not, return false. If it does, return match(child, index + 1).
     • Case 2 (Wildcard): If the character is ., iterate through all 26 indices of the current node's children array.
       • For every existing child, call match(child, index + 1).
       • If any call returns true, propagate true upwards immediately.
       • If the loop finishes without success, return false.

Execution Flow

Consider addWord("bad") followed by search("b.d").

1. Initialization: root node created.
2. addWord("bad"):
   • Current: root. Char: 'b'. root.children['b'] is null $\to$ create new Node 1. Move to Node 1.
   • Current: Node 1. Char: 'a'. Node1.children['a'] is null $\to$ create new Node 2. Move to Node 2.
   • Current: Node 2. Char: 'd'. Node2.children['d'] is null $\to$ create new Node 3. Move to Node 3.
   • End of word. Set Node3.isEnd = true.
3. search("b.d"):
   • Call helper match(root, 0).
   • Index 0 (char 'b'): It is not .. Check root.children['b']. It exists (Node 1). Recurse: match(Node 1, 1).
   • Index 1 (char '.'): It is .. Iterate 0..25 on Node 1's children.
     • Found child at 'a' (Node 2). Recurse: match(Node 2, 2).
   • Index 2 (char 'd'): It is not .. Check Node 2.children['d']. It exists (Node 3). Recurse: match(Node 3, 3).
   • Index 3 (End of string): Return Node3.isEnd (which is true).
   • The recursion unwinds returning true.

Proof of Correctness

The algorithm is correct because the Trie structure represents a complete state machine of all valid prefixes added to the dictionary.

• Invariant: A path from the root to a node marked isEnd represents exactly one word added to the dictionary.
• Completeness: The addWord function ensures all characters are stored in sequence.
• Search Logic: The search function explores paths. For literal characters, it prunes the search space immediately if a match is not found. For wildcards, it exhaustively checks all valid transitions (existing children). Since the wildcard . matches any character, checking all existing children covers all possible valid matches in the dictionary. If a path exists that satisfies the pattern and ends at an isEnd node, the algorithm is guaranteed to find it.

Pattern Reuse Notes

The Trie pattern with DFS traversal is a powerful tool for string problems. Similar techniques apply to:

• LeetCode 208: Implement Trie (Prefix Tree) - The foundational problem for this structure.
• LeetCode 720: Longest Word in Dictionary - Uses Trie traversal to find words built from other words.
• LeetCode 648: Replace Words - Uses Trie for finding the shortest root prefix.
• LeetCode 425: Word Squares - Advanced backtracking on a Trie structure.

Understanding LeetCode 211 solidifies the concept of modifying standard data structure traversals to fit specific constraints (like wildcards).

Reference Implementation

C++ Solution for LeetCode 211

1class WordDictionary {
2private:
3    struct TrieNode {
4        TrieNode* children[26];
5        bool isEnd;
6        
7        TrieNode() {
8            isEnd = false;
9            for (int i = 0; i < 26; i++) {
10                children[i] = nullptr;
11            }
12        }
13    };
14    
15    TrieNode* root;
16
17    bool searchHelper(TrieNode* node, string& word, int index) {
18        // Base case: if we have reached the end of the word
19        if (index == word.length()) {
20            return node->isEnd;
21        }
22
23        char c = word[index];
24
25        if (c == '.') {
26            // If wildcard, try all possible children
27            for (int i = 0; i < 26; i++) {
28                if (node->children[i] != nullptr) {
29                    if (searchHelper(node->children[i], word, index + 1)) {
30                        return true;
31                    }
32                }
33            }
34            return false;
35        } else {
36            // If literal character, move to specific child
37            int charIndex = c - 'a';
38            if (node->children[charIndex] == nullptr) {
39                return false;
40            }
41            return searchHelper(node->children[charIndex], word, index + 1);
42        }
43    }
44
45public:
46    WordDictionary() {
47        root = new TrieNode();
48    }
49    
50    void addWord(string word) {
51        TrieNode* curr = root;
52        for (char c : word) {
53            int index = c - 'a';
54            if (curr->children[index] == nullptr) {
55                curr->children[index] = new TrieNode();
56            }
57            curr = curr->children[index];
58        }
59        curr->isEnd = true;
60    }
61    
62    bool search(string word) {
63        return searchHelper(root, word, 0);
64    }
65};

Java Solution for LeetCode 211

1class WordDictionary {
2    
3    private class TrieNode {
4        TrieNode[] children;
5        boolean isEnd;
6
7        public TrieNode() {
8            children = new TrieNode[26];
9            isEnd = false;
10        }
11    }
12
13    private TrieNode root;
14
15    public WordDictionary() {
16        root = new TrieNode();
17    }
18    
19    public void addWord(String word) {
20        TrieNode curr = root;
21        for (char c : word.toCharArray()) {
22            int index = c - 'a';
23            if (curr.children[index] == null) {
24                curr.children[index] = new TrieNode();
25            }
26            curr = curr.children[index];
27        }
28        curr.isEnd = true;
29    }
30    
31    public boolean search(String word) {
32        return searchHelper(root, word, 0);
33    }
34
35    private boolean searchHelper(TrieNode node, String word, int index) {
36        if (index == word.length()) {
37            return node.isEnd;
38        }
39
40        char c = word.charAt(index);
41
42        if (c == '.') {
43            for (int i = 0; i < 26; i++) {
44                if (node.children[i] != null) {
45                    if (searchHelper(node.children[i], word, index + 1)) {
46                        return true;
47                    }
48                }
49            }
50            return false;
51        } else {
52            int charIndex = c - 'a';
53            if (node.children[charIndex] == null) {
54                return false;
55            }
56            return searchHelper(node.children[charIndex], word, index + 1);
57        }
58    }
59}

Python Solution for LeetCode 211

1class TrieNode:
2    def __init__(self):
3        self.children = {}
4        self.is_end = False
5
6class WordDictionary:
7
8    def __init__(self):
9        self.root = TrieNode()
10
11    def addWord(self, word: str) -> None:
12        curr = self.root
13        for char in word:
14            if char not in curr.children:
15                curr.children[char] = TrieNode()
16            curr = curr.children[char]
17        curr.is_end = True
18
19    def search(self, word: str) -> bool:
20        
21        def dfs(node, index):
22            # Base case: end of word reached
23            if index == len(word):
24                return node.is_end
25            
26            char = word[index]
27            
28            if char == '.':
29                # Try all existing children
30                for child in node.children.values():
31                    if dfs(child, index + 1):
32                        return True
33                return False
34            else:
35                # Standard Trie traversal
36                if char not in node.children:
37                    return False
38                return dfs(node.children[char], index + 1)
39        
40        return dfs(self.root, 0)