Design Add and Search Words Data Structure (LC 211): Trie + DFS

Design a WordDictionary with addWord and search, where '.' in a query matches any letter. Store words in a trie and branch into every child at each '.': O(L) per add, O(26^d * L) per search with d dots.

Language Selection

Choose your preferred programming language

Showing: Python

Design Add and Search Words Data Structure

Problem Statement

Build a class WordDictionary that stores words and answers pattern queries:

  • WordDictionary() creates an empty dictionary.
  • addWord(word) stores word.
  • search(word) returns true if some stored word matches the pattern word, otherwise false. The pattern may contain the character '.', which matches exactly one letter of any kind. Every other character must match itself, and the stored word must have the same length as the pattern.

Examples

Example 1:

Input:
["WordDictionary", "addWord", "addWord", "addWord", "search", "search", "search", "search", "search"]
[[], ["pen"], ["pin"], ["pig"], ["p.n"], ["pe"], ["..g"], ["pen"], ["p..."]]
Output:
[null, null, null, null, true, false, true, true, false]
Explanation:
"p.n" matches "pen" and "pin".
"pe" is only a prefix of "pen", so it is not a match.
"..g" matches "pig".
"p..." needs a 4-letter word starting with p; there is none.

Example 2:

Input:
["WordDictionary", "search", "addWord", "search", "search"]
[[], ["."], ["a"], ["."], [".."]]
Output:
[null, false, null, true, false]
Explanation:
Nothing is stored at first. After adding "a", the one-letter pattern "." matches it,
but ".." needs two letters.

Constraints

  • 1 <= word.length <= 25
  • word in addWord consists of lowercase English letters
  • word in search consists of '.' or lowercase English letters, with at most 2 dots per query
  • At most 10^4 calls in total are made to addWord and search

Approach 1: Bucket Words by Length

Algorithm

A match must have exactly the pattern’s length, so group the stored words by length. A query only has to compare against the words in one bucket.

  1. addWord(word): append word to the list for len(word).
  2. search(pattern): for each word in the bucket for len(pattern), compare character by character, treating '.' as matching anything. Return true on the first full match.
  3. If no word in the bucket matches (or the bucket is empty), return false.

Implementation

Python:

from collections import defaultdict


class WordDictionary:
    def __init__(self):
        self.by_length = defaultdict(list)   # length -> words of that length

    def addWord(self, word: str) -> None:
        self.by_length[len(word)].append(word)

    def search(self, word: str) -> bool:
        # Only words of the same length can match
        for candidate in self.by_length.get(len(word), []):
            if all(p == '.' or p == c for p, c in zip(word, candidate)):
                return True
        return False

Java:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class WordDictionary {
    private final Map<Integer, List<String>> byLength = new HashMap<>();

    public WordDictionary() {
    }

    public void addWord(String word) {
        byLength.computeIfAbsent(word.length(), len -> new ArrayList<>()).add(word);
    }

    public boolean search(String word) {
        // Only words of the same length can match
        for (String candidate : byLength.getOrDefault(word.length(), List.of())) {
            if (matches(word, candidate)) return true;
        }
        return false;
    }

    private static boolean matches(String pattern, String candidate) {
        for (int i = 0; i < pattern.length(); i++) {
            char p = pattern.charAt(i);
            if (p != '.' && p != candidate.charAt(i)) return false;
        }
        return true;
    }
}

Go:

type WordDictionary struct {
	byLength map[int][]string // length -> words of that length
}

func Constructor() WordDictionary {
	return WordDictionary{byLength: map[int][]string{}}
}

func (this *WordDictionary) AddWord(word string) {
	this.byLength[len(word)] = append(this.byLength[len(word)], word)
}

func (this *WordDictionary) Search(word string) bool {
	// Only words of the same length can match
	for _, candidate := range this.byLength[len(word)] {
		match := true
		for i := 0; i < len(word); i++ {
			if word[i] != '.' && word[i] != candidate[i] {
				match = false
				break
			}
		}
		if match {
			return true
		}
	}
	return false
}

JavaScript:

class WordDictionary {
    constructor() {
        this.byLength = new Map(); // length -> words of that length
    }

    /** @param {string} word @return {void} */
    addWord(word) {
        if (!this.byLength.has(word.length)) {
            this.byLength.set(word.length, []);
        }
        this.byLength.get(word.length).push(word);
    }

    /** @param {string} word @return {boolean} */
    search(word) {
        // Only words of the same length can match
        const bucket = this.byLength.get(word.length) || [];
        return bucket.some(candidate => {
            for (let i = 0; i < word.length; i++) {
                if (word[i] !== '.' && word[i] !== candidate[i]) return false;
            }
            return true;
        });
    }
}

C#:

using System.Collections.Generic;

public class WordDictionary {
    private readonly Dictionary<int, List<string>> byLength = new Dictionary<int, List<string>>();

    public WordDictionary() {
    }

    public void AddWord(string word) {
        if (!byLength.TryGetValue(word.Length, out var bucket)) {
            bucket = new List<string>();
            byLength[word.Length] = bucket;
        }
        bucket.Add(word);
    }

    public bool Search(string word) {
        // Only words of the same length can match
        if (!byLength.TryGetValue(word.Length, out var candidates)) return false;
        foreach (string candidate in candidates) {
            if (Matches(word, candidate)) return true;
        }
        return false;
    }

    private static bool Matches(string pattern, string candidate) {
        for (int i = 0; i < pattern.Length; i++) {
            if (pattern[i] != '.' && pattern[i] != candidate[i]) return false;
        }
        return true;
    }
}

C++:

#include <string>
#include <unordered_map>
#include <vector>
using namespace std;

class WordDictionary {
public:
    WordDictionary() {}

    void addWord(string word) {
        byLength[word.size()].push_back(word);
    }

    bool search(string word) {
        // Only words of the same length can match
        auto it = byLength.find(word.size());
        if (it == byLength.end()) return false;
        for (const string& candidate : it->second) {
            if (matches(word, candidate)) return true;
        }
        return false;
    }

private:
    unordered_map<size_t, vector<string>> byLength;  // length -> words of that length

    static bool matches(const string& pattern, const string& candidate) {
        for (size_t i = 0; i < pattern.size(); i++) {
            if (pattern[i] != '.' && pattern[i] != candidate[i]) return false;
        }
        return true;
    }
};

Complexity Analysis

  • Time: addWord is O(L) (amortized, counting the copy or hash of the word). search is O(K * L), where K is the number of stored words with the pattern’s length; in the worst case all N words have that length, so O(N * L).
  • Space: O(total characters added).

Approach 2: Trie with DFS on Wildcards (Optimal)

Algorithm

Store the words in a trie (see Implement Trie). A plain letter in the pattern follows exactly one child link, just like a normal trie lookup. A '.' can be any letter, so the search branches into every existing child at that position.

  1. addWord(word): standard trie insert, marking the last node as a word end.
  2. search(pattern): run dfs(node, i), meaning “can the rest of the pattern, starting at index i, be matched from node?”
    • If i == len(pattern), return whether node is a word end (this enforces the exact length).
    • If pattern[i] is a letter, follow that child; if it is missing, return false.
    • If pattern[i] is '.', try dfs(child, i + 1) for every child and return true as soon as one succeeds.
  3. The recursion depth is at most the pattern length (25), so recursion is safe here.

The trie prunes as it goes: a branch that has no stored continuation is abandoned immediately, which the bucket approach cannot do.

Implementation

Python:

class TrieNode:
    __slots__ = ("children", "is_end")

    def __init__(self):
        self.children = {}    # char -> TrieNode
        self.is_end = False


class WordDictionary:
    def __init__(self):
        self.root = TrieNode()

    def addWord(self, word: str) -> None:
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def search(self, word: str) -> bool:
        def dfs(node, i):
            if i == len(word):
                return node.is_end            # pattern used up: must end a word here
            ch = word[i]
            if ch == '.':
                # Wildcard: any existing child may continue the match
                return any(dfs(child, i + 1) for child in node.children.values())
            child = node.children.get(ch)
            return child is not None and dfs(child, i + 1)

        return dfs(self.root, 0)

Java:

class WordDictionary {
    private static class Node {
        final Node[] children = new Node[26];
        boolean isEnd;
    }

    private final Node root = new Node();

    public WordDictionary() {
    }

    public void addWord(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            int c = word.charAt(i) - 'a';
            if (node.children[c] == null) {
                node.children[c] = new Node();
            }
            node = node.children[c];
        }
        node.isEnd = true;
    }

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

    private boolean dfs(Node node, String word, int i) {
        if (i == word.length()) {
            return node.isEnd;               // pattern used up: must end a word here
        }
        char ch = word.charAt(i);
        if (ch == '.') {
            // Wildcard: any existing child may continue the match
            for (Node child : node.children) {
                if (child != null && dfs(child, word, i + 1)) return true;
            }
            return false;
        }
        Node child = node.children[ch - 'a'];
        return child != null && dfs(child, word, i + 1);
    }
}

Go:

type trieNode struct {
	children [26]*trieNode
	isEnd    bool
}

type WordDictionary struct {
	root *trieNode
}

func Constructor() WordDictionary {
	return WordDictionary{root: &trieNode{}}
}

func (this *WordDictionary) AddWord(word string) {
	node := this.root
	for i := 0; i < len(word); i++ {
		c := word[i] - 'a'
		if node.children[c] == nil {
			node.children[c] = &trieNode{}
		}
		node = node.children[c]
	}
	node.isEnd = true
}

func (this *WordDictionary) Search(word string) bool {
	var dfs func(node *trieNode, i int) bool
	dfs = func(node *trieNode, i int) bool {
		if i == len(word) {
			return node.isEnd // pattern used up: must end a word here
		}
		if word[i] == '.' {
			// Wildcard: any existing child may continue the match
			for _, child := range node.children {
				if child != nil && dfs(child, i+1) {
					return true
				}
			}
			return false
		}
		child := node.children[word[i]-'a']
		return child != nil && dfs(child, i+1)
	}
	return dfs(this.root, 0)
}

JavaScript:

class TrieNode {
    constructor() {
        this.children = new Map(); // char -> TrieNode
        this.isEnd = false;
    }
}

class WordDictionary {
    constructor() {
        this.root = new TrieNode();
    }

    /** @param {string} word @return {void} */
    addWord(word) {
        let node = this.root;
        for (const ch of word) {
            if (!node.children.has(ch)) {
                node.children.set(ch, new TrieNode());
            }
            node = node.children.get(ch);
        }
        node.isEnd = true;
    }

    /** @param {string} word @return {boolean} */
    search(word) {
        const dfs = (node, i) => {
            if (i === word.length) {
                return node.isEnd;            // pattern used up: must end a word here
            }
            const ch = word[i];
            if (ch === '.') {
                // Wildcard: any existing child may continue the match
                for (const child of node.children.values()) {
                    if (dfs(child, i + 1)) return true;
                }
                return false;
            }
            const child = node.children.get(ch);
            return child !== undefined && dfs(child, i + 1);
        };
        return dfs(this.root, 0);
    }
}

C#:

public class WordDictionary {
    private class Node {
        public readonly Node[] Children = new Node[26];
        public bool IsEnd;
    }

    private readonly Node root = new Node();

    public WordDictionary() {
    }

    public void AddWord(string word) {
        Node node = root;
        foreach (char ch in word) {
            int c = ch - 'a';
            if (node.Children[c] == null) {
                node.Children[c] = new Node();
            }
            node = node.Children[c];
        }
        node.IsEnd = true;
    }

    public bool Search(string word) {
        return Dfs(root, word, 0);
    }

    private static bool Dfs(Node node, string word, int i) {
        if (i == word.Length) {
            return node.IsEnd;               // pattern used up: must end a word here
        }
        char ch = word[i];
        if (ch == '.') {
            // Wildcard: any existing child may continue the match
            foreach (Node child in node.Children) {
                if (child != null && Dfs(child, word, i + 1)) return true;
            }
            return false;
        }
        Node next = node.Children[ch - 'a'];
        return next != null && Dfs(next, word, i + 1);
    }
}

C++:

#include <memory>
#include <string>
using namespace std;

class WordDictionary {
public:
    WordDictionary() : root(make_unique<Node>()) {}

    void addWord(string word) {
        Node* node = root.get();
        for (char ch : word) {
            int c = ch - 'a';
            if (!node->children[c]) {
                node->children[c] = make_unique<Node>();
            }
            node = node->children[c].get();
        }
        node->isEnd = true;
    }

    bool search(string word) {
        return dfs(root.get(), word, 0);
    }

private:
    struct Node {
        unique_ptr<Node> children[26];
        bool isEnd = false;
    };

    unique_ptr<Node> root;

    static bool dfs(const Node* node, const string& word, size_t i) {
        if (i == word.size()) {
            return node->isEnd;              // pattern used up: must end a word here
        }
        char ch = word[i];
        if (ch == '.') {
            // Wildcard: any existing child may continue the match
            for (const auto& child : node->children) {
                if (child && dfs(child.get(), word, i + 1)) return true;
            }
            return false;
        }
        const Node* next = node->children[ch - 'a'].get();
        return next != nullptr && dfs(next, word, i + 1);
    }
};

Complexity Analysis

  • Time: addWord is O(L). search is O(L) when the pattern has no dots. Each dot can branch into at most 26 children, so a pattern with d dots visits at most O(26^d * L) nodes, and never more than the total number of trie nodes. With at most 2 dots that is bounded by 676 * 25 steps per query.
  • Space: O(T) for the trie, where T is the total number of characters added, plus O(L) recursion depth during search.

Key Insights

  1. A wildcard turns a trie lookup into a DFS. Letters follow one link; a dot fans out to all children, and the first successful branch ends the search.
  2. The end-of-word check enforces the length. Reaching the end of the pattern is only a match if that node ends a stored word; otherwise “pe” would match “pen”.
  3. The trie prunes shared failures. If no stored word starts with “px”, every pattern starting with “px” is rejected after two steps, regardless of how many words exist.
  4. Short words make recursion safe. The depth is bounded by the pattern length (25 here), unlike tree problems where depth can reach the number of nodes.

Edge Cases

  • Search before any add: the root has no children, so every pattern returns false.
  • Pattern of only dots: "..." is true exactly when some stored word has length 3.
  • Pattern is a strict prefix of a stored word: "pe" with only "pen" stored returns false.
  • Pattern longer than every stored word: the walk runs out of children and returns false.
  • Duplicate adds: adding the same word twice changes nothing in the trie.
  • Dot in the last position: the DFS must still check the end flag on each child it tries.

Common Mistakes

  1. Returning true when the pattern is used up, without checking isEnd. That accepts prefixes of stored words.
  2. Stopping after the first child on a dot. If the first branch fails, the remaining children must still be tried.
  3. Iterating null children. In array-based tries, skip empty slots before recursing.
  4. Treating '.' as “zero or more” characters. Here it matches exactly one letter, unlike regex .*.
  5. Using a regex per stored word. It works, but it costs O(N * L) per query and hides the intended data structure.

Interview Tips

  1. Start from the plain trie and ask, “what changes when one character can be anything?” The answer is a single branching case.
  2. Mention the length-bucket approach as a simple baseline; it is easy to get right and shows you thought about pruning by length.
  3. Bring up the “at most 2 dots” constraint when giving the search complexity; it is why the trie stays fast.
  4. Explain why recursion is fine here (depth at most 25) even though you would avoid it on deep trees.
  5. Walk through a failing dot branch to show the backtracking works.

Follow-up Questions

  1. What if '*' could match any sequence of letters (including none)? At a star, try both “consume no letters and move to the next pattern character” and “consume one letter (any child) and stay on the star”. Memoize on (node, i) to avoid repeated work.
  2. What if searches vastly outnumber adds and patterns have many dots? Precompute, for each word, all of its variants with dots in up to d positions and store them in a hash set; search becomes O(L), at the cost of O(C(L, d) * L) storage per word.
  3. How would you return all matching words instead of a boolean? Do not stop at the first success; collect every word end reached when the pattern is used up.
  4. How would you support deleting a word? Clear its end flag and remove nodes on the way back up that no longer have children or an end flag.