Add and Search Word Data Structure Implementation

This solution implements a word dictionary system that supports adding words and searching for words with wildcard characters, demonstrating efficient Trie-based data structure design for fast lookups and flexible pattern matching.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. What is the maximum expected size of the word dictionary and number of search operations?
2. Are we allowed to modify the input data structure during searches, or must it remain immutable?
3. Do we need to support case-insensitive matching, or is exact matching sufficient?
4. Can the search string contain wildcards (e.g., dots) that match any character?
5. What is the expected time complexity for search operations? Should we aim for O(1) or O(log n) average?

Restatement in my own words: We need to implement a data structure that supports two operations: adding new words to a dictionary and searching for whether a given word exists in the dictionary. The search operation should also handle wildcard characters (dots) that can match any single character.

Problem constraints and inputs:

• Input consists of a dictionary that supports adding words (strings) and searching for words
• Search strings may contain dots (.) as wildcards that match any single character
• All words consist of lowercase letters only (a-z)
• The dictionary can contain duplicate words, though this is not explicitly required
• Search operations should return true if the pattern matches any word in the dictionary

Assumptions I'm making:

• The search string can contain dots (.) as wildcards, matching any single character
• Words are composed only of lowercase English letters (a-z)
• The dictionary supports efficient insertion and search operations
• We can modify the internal data structure during add operations but must preserve correctness

Data shape and hidden structure: The problem involves a set of variable-length strings with wildcard matching capability. The key insight is that we're dealing with a string matching problem where we need to efficiently handle both exact matches and pattern matching with wildcards. The structure is essentially a set of words that need to support prefix-based searching or full pattern matching with wildcards.

2. Pattern Recognition

The problem involves implementing a data structure that supports two operations: adding words and searching for words with support for wildcard characters ('.'). This pattern is most closely aligned with Trie (Prefix Tree) data structure usage.

The key indicators that signal this pattern:

• Word-based operations: We're dealing with strings and their prefixes, which is classic Trie territory
• Wildcard matching: The '.' character suggests we need to handle branching search paths, which is a common extension of Trie operations
• Dynamic insertion and lookup: The requirement to add words dynamically while searching suggests we need a mutable prefix structure

The core insight is that this problem requires building a Trie with wildcard support. When we encounter a '.', we need to explore all possible child branches rather than following a single path, which is the key difference from standard prefix matching.

This pattern appears in problems where:

• We need to efficiently store and search for words with prefix constraints
• Wildcard characters introduce branching logic in search operations
• The data structure must support both insertion and flexible pattern matching

The fundamental approach is to build a Trie where each node represents a character, and search operations must handle the special case of '.' by exploring all valid child paths.

3. Approach Evolution

My first instinct is to use a brute force approach where I store all words in a list and for each search, I check every word to see if it matches the pattern. But that's O(n*m) where n is the number of words and m is the average word length, because for each search we might have to scan through all stored words. That's inefficient and not scalable.

Let me think about how to optimize this. I notice that when we search for a word with dots (wildcards), we're essentially looking for any word that matches the pattern. This suggests we should think about prefix matching and how to efficiently find words that match a given pattern.

I notice that if I maintain the words in a way that allows me to quickly find all words with a specific prefix, I can reduce the search time. The key insight is that for wildcard searches, I need to be able to explore all possible paths in a prefix structure.

The core insight is that we can use a Trie (prefix tree) data structure to store the words. When searching with dots, I can perform a depth-first search through the trie, trying all possible paths at wildcard positions. This reduces the search to O(m) where m is the length of the search word, assuming we're searching for a specific word rather than all matches.

Let me think about the invariants I need to maintain:

1. The trie must properly represent all inserted words
2. When searching with wildcards, I need to explore all possible character paths at dot positions
3. The search must correctly handle the end-of-word markers in the trie

The approach I'll take is to build a Trie structure where:

• Each node represents a character
• We track word endings with a flag or special marker
• For search operations, we use DFS to handle wildcards by trying all child paths when we encounter a dot

This is more efficient than the brute force approach because:

• Insertion is O(m) where m is word length
• Search with wildcards becomes O(d) where d is the depth of the trie (max word length)
• We avoid re-scanning all stored words for each search query

The key optimization is using the trie's prefix property to avoid redundant comparisons and leveraging backtracking for wildcard handling.

4. Data Structure Choice

For this problem, I need to design a data structure that supports two operations efficiently: adding words and searching for words with wildcards. The key insight is that I need to balance between fast insertion and fast searching.

The primary data structure I'll use is a Trie (Prefix Tree). This is the most appropriate choice because:

• It naturally supports prefix-based searching
• It allows efficient insertion of words
• It can handle wildcard matching (the '.' character) by exploring all possible branches

For the Trie implementation, I'll use:

• A TrieNode class with:
  • An array of 26 TrieNode references (one for each lowercase letter)
  • A boolean flag to mark the end of a word

I'll also maintain a root TrieNode as the entry point to the trie structure.

The choice of Trie over other structures like hash tables or arrays is driven by:

• Hash tables would require storing all possible wildcard combinations, leading to exponential space usage
• Arrays would not provide efficient prefix matching for search operations
• Trie provides optimal space efficiency and time complexity for this specific use case

The wildcard '.' character requires special handling during search - I need to explore all 26 possible child nodes when encountering a dot, which is naturally supported by the Trie structure.

Time complexity for insertion and search operations in the Trie is O(m) where m is the length of the word, which is optimal for this problem's requirements.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to show how it works step-by-step.

Example: addWord("bad"), addWord("dad"), addWord("mad"), then search for "pad" and "b.."

Step 1: Add "bad"

• Create new TrieNode for 'b'
• Create new TrieNode for 'a'
• Create new TrieNode for 'd'
• Mark end of word at 'd' node

Step 2: Add "dad"

• Navigate to existing 'd' node from previous step
• Create new TrieNode for 'a'
• Create new TrieNode for 'd'
• Mark end of word at 'd' node

Step 3: Add "mad"

• Navigate to existing 'm' node (new path)
• Create new TrieNode for 'a'
• Create new TrieNode for 'd'
• Mark end of word at 'd' node

Step 4: Search "pad"

• Start from root, look for 'p' - not found
• Return false immediately

Step 5: Search "b.."

• Start from root, navigate to 'b' node
• At position 1 ('.'), try all 26 possible children from 'b' node
• For each child, recursively search remaining pattern "d"
• Find matching path through 'b' → 'a' → 'd'
• Return true

The key insight is that when we encounter a '.', we must explore all possible child paths recursively, maintaining the correct trie traversal state at each recursive call. The search function uses backtracking to explore all valid paths.

public boolean search(String word) {
    return searchHelper(word, 0, root);
}

private boolean searchHelper(String word, int index, TrieNode node) {
    // Base case: reached end of word
    if (index == word.length()) {
        return node.isEnd;
    }
    
    char c = word.charAt(index);
    
    if (c == '.') {
        // Wildcard: try all possible children
        for (TrieNode child : node.children) {
            if (child != null && searchHelper(word, index + 1, child)) {
                return true;
            }
        }
        return false; // No matching path found
    } else {
        // Normal character: follow exact path
        TrieNode next = node.children[c - 'a'];
        if (next == null) {
            return false; // Character not found
        }
        return searchHelper(word, index + 1, next);
    }
}

6. Java Solution

class WordDictionary {
    private static class TrieNode {
        TrieNode[] children;
        boolean isEndOfWord;
        
        public TrieNode() {
            children = new TrieNode[26]; // For each lowercase letter
            isEndOfWord = false;
        }
    }
    
    private TrieNode root;
    
    public WordDictionary() {
        root = new TrieNode();
    }
    
    public void addWord(String word) {
        TrieNode current = root;
        
        // Traverse the trie, creating nodes as needed
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (current.children[index] == null) {
                current.children[index] = new TrieNode();
            }
            current = current.children[index];
        }
        
        // Mark end of word
        current.isEndOfWord = true;
    }
    
    public boolean search(String word) {
        return searchHelper(word, 0, root);
    }
    
    private boolean searchHelper(String word, int index, TrieNode node) {
        // Base case: reached end of word
        if (index == word.length()) {
            return node.isEndOfWord;
        }
        
        char c = word.charAt(index);
        
        if (c == '.') {
            // Wildcard: try all possible children
            for (TrieNode child : node.children) {
                if (child != null && searchHelper(word, index + 1, child)) {
                    return true;
                }
            }
            return false;
        } else {
            // Regular character: follow exact path
            int childIndex = c - 'a';
            TrieNode child = node.children[childIndex];
            
            if (child == null) {
                return false;
            }
            
            return searchHelper(word, index + 1, child);
        }
    }
}

This solution implements a Trie (prefix tree) data structure to efficiently store and search words with wildcard support. The key insight is that we need to handle the '.' wildcard character specially by trying all possible paths when it appears. The solution uses a recursive helper method to handle the wildcard case, which is clean and readable while maintaining optimal performance characteristics.

7. Complexity Analysis

Time Complexity: O(M × N) where M is the average length of words in the dictionary and N is the number of words in the dictionary.

For the addWord operation, we perform O(M) work to insert a word into the Trie structure, where M is the length of the word.

For the search operation:

• In the worst case, we need to traverse all nodes in the Trie for a word of length M, which takes O(M) time.
• If there are N words in the dictionary, and we're searching for a word that matches all of them (or requires backtracking), the complexity becomes O(M × N) in the worst case.

Space Complexity: O(ALPHABET_SIZE × M × N) where:

• ALPHABET_SIZE = 26 (for lowercase English letters)
• M is the average length of words in the dictionary
• N is the number of words in the dictionary

In the worst case, we might store all words in the Trie structure, requiring space proportional to the total number of characters across all words. Each node in the Trie can have up to 26 children (for each letter), and we store one node per character in the words.

Why these bounds are correct: The time complexity is linear with respect to the word length and dictionary size because we process each character once during insertion and search operations. The space complexity accounts for the maximum possible nodes in a Trie structure that could be created from N words of average length M.

Optimality: This solution is optimal for the given constraints where we need to support both insertion and search operations efficiently. The Trie structure provides the best balance between time and space complexity for this type of prefix-based searching problem, achieving O(M) search time where M is the word length rather than O(N × M) in a linear search approach.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty word list: When no words exist, all search operations should return false
• Single character words: Must handle single character searches correctly, especially with wildcards
• Empty search string: Should return false for empty search queries

Duplicate Values and Repeated States

• Duplicate words: Adding the same word multiple times should not affect search behavior
• Repeated searches: Multiple searches for the same pattern should work consistently

Boundary Conditions

• Single character patterns: Both "a" and ".a" should work correctly
• Longest word matching: When searching for a very long pattern, ensure proper bounds checking
• Wildcard at beginning/end: Patterns like "..." or ".a." must be handled correctly

Common Implementation Mistakes

• Incorrect wildcard matching: Not properly handling . as a wildcard that matches any character
• State persistence issues: Using shared mutable state between search operations
• Off-by-one errors: Incorrect array bounds when checking character matches
• Missing null checks: Not validating input parameters before processing
• Inefficient string operations: Using String.substring() repeatedly instead of character-by-character comparison

Implementation Considerations

• Thread safety: If the class is used in concurrent environments, ensure thread-safe operations
• Memory management: For large word lists, avoid unnecessary memory allocation during searches
• Early termination: When a wildcard matches any character, ensure we don't continue unnecessary checks

The most critical pitfall is ensuring that wildcard matching works correctly - . should match any single character, not just lowercase letters, and the matching logic must be carefully validated against edge cases.

9. Alternative Approaches

There are several alternative approaches to solving the Add and Search Word problem, each with different trade-offs:

1. Trie-based Approach (Optimal for Multiple Operations) The most efficient approach for handling multiple add and search operations is to use a Trie (prefix tree) data structure. Each word is inserted into the trie, and search operations traverse the trie while handling wildcards. This approach has O(M) time complexity for both add and search operations, where M is the length of the word. The space complexity is O(ALPHABET_SIZE × N × M) where N is the number of words.

2. Hash Set with Wildcard Matching For search operations, we could maintain a HashSet of words and implement wildcard matching by checking each word in the set. This approach has O(N × M) time complexity for search operations where N is the number of words and M is the maximum word length. While simple to implement, it's inefficient for frequent searches.

3. Sorted Array with Binary Search If we maintain words in a sorted array, we could use binary search for exact matches and potentially optimize wildcard searches by filtering words with matching prefixes. However, this approach requires maintaining sorted order during insertions, which is O(N) for each insertion.

4. HashMap with Length-based Grouping We could group words by their lengths in a HashMap, where each key maps to a list of words with that length. This allows us to only search within the relevant length group during wildcard searches, reducing the search space but still requiring O(N) time for each search operation.

The chosen solution using HashSet with wildcard handling is preferred because it provides a good balance between simplicity, performance for the specific use case, and ease of implementation. The Trie approach would be better if we expect many more search operations than additions, but it's more complex to implement correctly.

The key trade-off is between implementation complexity and performance characteristics. The HashSet approach has O(1) average case for additions but O(N × M) worst-case for searches, while the Trie approach has consistent O(M) performance for both operations but with higher implementation complexity.

10. Test Cases

// Test case 1: Basic functionality with wildcards
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
assertTrue(wordDictionary.search("pad")); // false
assertTrue(wordDictionary.search("bad")); // true
assertTrue(wordDictionary.search(".ad")); // true
assertTrue(wordDictionary.search("b..")); // true

// Test case 2: Edge cases with empty strings and single characters
WordDictionary emptyDict = new WordDictionary();
assertFalse(emptyDict.search("")); // false - no words added
emptyDict.addWord("");
assertTrue(emptyDict.search(".")); // true - empty string matches wildcard

// Test case 3: Complex wildcard patterns
WordDictionary complexDict = new WordDictionary();
complexDict.addWord("abc");
complexDict.addWord("abd");
complexDict.addWord("abe");
assertTrue(complexDict.search("a.c")); // true - matches abc or abd or abe
assertFalse(complexDict.search("a.d")); // false - no match for a.d pattern

// Test case 4: Mixed length words with wildcards
WordDictionary mixedDict = new WordDictionary();
mixedDict.addWord("a");
mixedDict.addWord("ab");
mixedDict.addWord("abc");
assertTrue(mixedDict.search("a")); // true - exact match
assertTrue(mixedDict.search("a.")); // true - matches "ab"
assertFalse(mixedDict.search("a..")); // false - no 3-letter word starting with "a"
assertTrue(mixedDict.search("...")); // true - matches "abc"

// Test case 5: Duplicate handling
WordDictionary dupDict = new WordDictionary();
dupDict.addWord("test");
dupDict.addWord("test"); // duplicate - should not affect search
assertTrue(dupDict.search("test")); // true - matches the word
assertTrue(dupDict.search("t..t")); // true - wildcard pattern matches

The test cases cover:

1. Basic functionality with various wildcard patterns
2. Edge cases including empty strings and single character words
3. Complex multi-character wildcard matching
4. Mixed length word scenarios
5. Duplicate handling and robustness

Each test validates different aspects of the implementation to ensure correctness across various usage patterns.

11. Final Summary

The core idea is to implement a word dictionary that supports efficient insertion and searching with wildcard characters, solved optimally using a Trie data structure. This solution achieves O(M) time complexity for both operations where M is the length of the word being searched or inserted, making it highly efficient for large datasets. The key insight is leveraging the Trie's hierarchical structure to eliminate redundant character comparisons during search operations, particularly when handling wildcards, while maintaining clean separation between the word storage and pattern matching logic through proper data structure design.