211. Design Add and Search Words Data Structure

At a Glance

Topic: tries
Pattern: Trie + DFS on wildcards and DFS / backtracking
Difficulty: Medium
Companies: Amazon, Google, Meta, Uber, Microsoft
Frequency: High
LeetCode: 211

Problem (one-liner)

Design a dictionary with addWord(word) and searchWord(pattern) where pattern may contain lowercase letters or . matching any single character.

Recognition Cues

Wildcard search over stored vocabulary → trie branches out on .
Backtracking / DFS from trie node when hitting wildcard
Exact match still linear along edges when letters fixed

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

List + regex — slow rebuild / compile per query.
Trie + DFS — O(26^dots * L) worst for dotted patterns but matches interview expectation.

Optimal Solution

Go

package main

type WordDictionary struct {
	children [26]*WordDictionary
	isWord   bool
}

func Constructor() WordDictionary {
	return WordDictionary{}
}

func (dict *WordDictionary) AddWord(word string) {
	node := dict
	for index := range word {
		offset := int(word[index] - 'a')
		if node.children[offset] == nil {
			node.children[offset] = &WordDictionary{}
		}
		node = node.children[offset]
	}
	node.isWord = true
}

func (dict *WordDictionary) Search(word string) bool {
	var match func(int, *WordDictionary) bool
	match = func(position int, node *WordDictionary) bool {
		if node == nil {
			return false
		}
		if position == len(word) {
			return node.isWord
		}
		letter := word[position]
		if letter == '.' {
			for offset := range node.children {
				child := node.children[offset]
				if child != nil && match(position+1, child) {
					return true
				}
			}
			return false
		}
		offset := int(letter - 'a')
		return match(position+1, node.children[offset])
	}
	return match(0, dict)
}

JavaScript

class WordDictionary {
	constructor() {
		this.children = new Map();
		this.isWord = false;
	}

	addWord(word) {
		let node = this;
		for (let index = 0; index < word.length; index++) {
			const letter = word[index];
			if (!node.children.has(letter)) {
				node.children.set(letter, new WordDictionary());
			}
			node = node.children.get(letter);
		}
		node.isWord = true;
	}

	search(word) {
		const match = (position, node) => {
			if (node === undefined || node === null) {
				return false;
			}
			if (position === word.length) {
				return node.isWord;
			}
			const letter = word[position];
			if (letter === '.') {
				for (const child of node.children.values()) {
					if (match(position + 1, child)) {
						return true;
					}
				}
				return false;
			}
			return match(position + 1, node.children.get(letter));
		};
		return match(0, this);
	}
}