Solving Design Add and Search Words in Go: Step-by-Step Guide

Design Add and Search Words in Go: A Step-by-Step Guide

The "Design Add and Search Words Data Structure" problem (LeetCode 211) is a classic interview question that tests your understanding of the Trie (prefix tree) data structure and your ability to extend it with wildcard search capabilities. In this tutorial, we will walk through the problem, understand why a Trie is the right choice, and implement a complete solution in Go.

What Is the Problem?

You are asked to design a data structure that supports two operations:

AddWord(word): Inserts a word into the data structure.
Search(word): Returns true if the word exists in the data structure. The word may contain dots (.), where each dot can match any single letter.

For example, after adding the words "bad", "dad", and "mad", a search for "pad" returns false, "bad" returns true, and ".ad" or "b.." also returns true.

Why a Trie?

A Trie is a tree-like data structure where each node represents a character. Words sharing common prefixes share the same path from the root. This makes prefix-based lookups extremely efficient. For this problem, the wildcard . forces us to explore multiple branches at a given node, which is naturally handled by a recursive depth-first traversal of the Trie.

Alternative approaches like storing words in a hash map would require iterating over every word for wildcard searches, leading to poor performance. The Trie gives us an average time complexity proportional to the length of the query word rather than the total number of stored words.

Designing the Trie Node

Each Trie node needs two things: a map of child characters to child nodes, and a boolean flag indicating whether the node marks the end of a valid word.

package main

import "fmt"

// TrieNode represents a single node in the Trie.
type TrieNode struct {
    children map[byte]*TrieNode
    isEnd    bool
}

// NewTrieNode constructs and returns a new TrieNode.
func NewTrieNode() *TrieNode {
    return &TrieNode{
        children: make(map[byte]*TrieNode),
        isEnd:    false,
    }
}

Using a map for children is flexible and memory-efficient for sparse character sets. If you only deal with lowercase English letters, you could also use a fixed-size array of 26 pointers for slightly faster access.

Building the WordDictionary Structure

The WordDictionary struct wraps the Trie and exposes the AddWord and Search methods.

// WordDictionary supports adding words and searching with wildcards.
type WordDictionary struct {
    root *TrieNode
}

// Constructor initializes a new WordDictionary.
func Constructor() WordDictionary {
    return WordDictionary{
        root: NewTrieNode(),
    }
}

Implementing AddWord

Insertion is straightforward: walk down the Trie character by character, creating new nodes when a path does not exist, and mark the final node as the end of a word.

// AddWord inserts a word into the dictionary.
func (wd *WordDictionary) AddWord(word string) {
    node := wd.root
    for i := 0; i < len(word); i++ {
        ch := word[i]
        if _, ok := node.children[ch]; !ok {
            node.children[ch] = NewTrieNode()
        }
        node = node.children[ch]
    }
    node.isEnd = true
}

The time complexity of AddWord is O(L), where L is the length of the word, because we traverse one level of the Trie per character.

Implementing Search with Wildcards

The search operation is more interesting. When we encounter a normal character, we follow the corresponding child. When we encounter a dot (.), we must recursively try every child node. If any recursive path returns true, the search succeeds.

// Search returns true if the word exists in the dictionary.
// The word may contain '.' characters that match any letter.
func (wd *WordDictionary) Search(word string) bool {
    return searchHelper(wd.root, word, 0)
}

// searchHelper recursively searches the Trie starting from the given node.
func searchHelper(node *TrieNode, word string, index int) bool {
    // Base case: we've processed every character in the word.
    if index == len(word) {
        return node.isEnd
    }

    ch := word[index]

    if ch == '.' {
        // Wildcard: try every child branch.
        for _, child := range node.children {
            if searchHelper(child, word, index+1) {
                return true
            }
        }
        return false
    }

    // Regular character: follow the specific child if it exists.
    child, ok := node.children[ch]
    if !ok {
        return false
    }
    return searchHelper(child, word, index+1)
}

In the worst case, where the search word consists entirely of dots, the algorithm explores every possible path in the Trie. However, in practice, words are bounded in length and the branching factor is limited to 26 lowercase letters, so the search remains efficient for typical inputs.

Putting It All Together

Let's write a main function to demonstrate the full workflow: adding words and performing both exact and wildcard searches.

func main() {
    dict := Constructor()

    dict.AddWord("bad")
    dict.AddWord("dad")
    dict.AddWord("mad")

    fmt.Println(dict.Search("pad")) // false
    fmt.Println(dict.Search("bad")) // true
    fmt.Println(dict.Search(".ad")) // true
    fmt.Println(dict.Search("b..")) // true
    fmt.Println(dict.Search("...")) // true
    fmt.Println(dict.Search("b.d")) // true
    fmt.Println(dict.Search("ba.")) // true
    fmt.Println(dict.Search("b...")) // false
}

When you run this program, the output should be:

false
true
true
true
true
true
true
false

Best Practices

Choose the right child structure: A map is flexible and works well for arbitrary character sets. A fixed-size array is faster but only suitable when the alphabet is small and known in advance.
Use recursion carefully: The recursive search is elegant but can hit Go's stack limits for extremely long words. For production use with very long inputs, consider converting the recursion into an explicit stack-based DFS.
Avoid unnecessary allocations: Reuse the children map and only allocate nodes when needed. This keeps memory usage proportional to the actual content stored.
Consider lowercase normalization: If your input may contain mixed case, normalize words to lowercase before inserting and searching to ensure consistent behavior.
Test edge cases: Always test empty strings, single-character words, words with all wildcards, and searches for words longer than any stored word.

Complexity Analysis

For AddWord, both time and space complexity are O(L) per word, where L is the word length. For Search, the best case (no wildcards) is O(L). The worst case, where every character is a wildcard, is O(26^L) in theory, but in practice it is bounded by the number of nodes in the Trie, making it O(N) where N is the total number of nodes.

Conclusion

The "Design Add and Search Words" problem is an excellent exercise for mastering the Trie data structure and recursive search techniques. By combining a simple Trie with a depth-first wildcard search, you get a clean, efficient solution that handles both exact and pattern-based lookups. Understanding this pattern will serve you well in interviews and in real-world applications such as autocomplete systems, spell checkers, and dictionary-based text processing tools.