211. Design Add And Search Words Data Structure - Explanation

Description

Design a data structure that supports adding new words and searching for existing words.

Implement the WordDictionary class:

void addWord(word) Adds word to the data structure.
bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.

Example 1:

Input:
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["day"],["bay"],["may"],["say"],["day"],[".ay"],["b.."]]

Output:
[null, null, null, null, false, true, true, true]

Explanation:
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("day");
wordDictionary.addWord("bay");
wordDictionary.addWord("may");
wordDictionary.search("say"); // return false
wordDictionary.search("day"); // return true
wordDictionary.search(".ay"); // return true
wordDictionary.search("b.."); // return true

Constraints:

1 <= word.length <= 20
word in addWord consists of lowercase English letters.
word in search consist of '.' or lowercase English letters.
There will be at most 2 dots in word for search queries.
At most 10,000 calls will be made to addWord and search.

Topics

Recommended Time & Space Complexity

You should aim for a solution with O(n) time for each function call and O(t + n) space, where n is the length of the string and t is the total number of nodes created in the Trie.

Hint 1

A brute force solution would be to store each added word in a list and search linearly through the list for a word every time. This would be an O(m * n) solution, where m is the size of the list and n is the length of the string. Can you think of a better way? Maybe there is a tree-like data structure.

Hint 2

We can use a Trie to implement adding and searching for words efficiently. Adding a word follows the standard Trie insertion process. However, when searching for a word containing '.', which can match any character, we need a different approach. Instead of directly matching, we consider all possible characters at the position of '.' and recursively check the rest of the word for each possibility. How would you implement it?

Hint 3

We traverse the word with index i, starting at the root of the Trie. For normal characters, we search as usual. When encountering a dot ('.'), we try all possible characters by recursively extending the search in each direction. If any path leads to a valid word, we return true; otherwise, we return false. Although we try all paths for a dot, the time complexity is still O(n) because there are at most two dots ('.') in the word, making the complexity O((26^2) * n).

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Trie (Prefix Tree) - A tree-like data structure used for efficient storage and retrieval of strings
Depth-First Search (DFS) - Used to traverse the Trie when encountering wildcard characters
Recursion - The DFS approach uses recursive calls to explore all possible character matches for wildcards

1. Brute Force

Intuition

The simplest way to solve this problem is to store all words as-is and check every stored word during search.

When searching:

If the lengths don't match → it can't be a match.
Compare characters one by one:
- Exact match is required unless the search character is .
- . acts as a wildcard and can match any character.

This approach works because the constraints are small enough, but it is not efficient for large datasets.

Algorithm

Data Structure

Maintain a list to store all added words.

addWord(word)

Append the word to the list.

search(word)

Loop through every stored word:
- Skip if lengths differ.
Compare characters index by index:
- If characters match → continue.
- If search character is . → treat as match.
- Otherwise → stop checking this word.
If all characters match → return true.
If no word matches → return false.

class WordDictionary:

    def __init__(self):
        self.store = []

    def addWord(self, word: str) -> None:
        self.store.append(word)

    def search(self, word: str) -> bool:
        for w in self.store:
            if len(w) != len(word):
                continue
            i = 0
            while i < len(w):
                if w[i] == word[i] or word[i] == '.':
                    i += 1
                else:
                    break
            if i == len(w):
                return True
        return False

public class WordDictionary {

    private List<String> store;

    public WordDictionary() {
        store = new ArrayList<>();
    }

    public void addWord(String word) {
        store.add(word);
    }

    public boolean search(String word) {
        for (String w : store) {
            if (w.length() != word.length()) continue;
            int i = 0;
            while (i < w.length()) {
                if (w.charAt(i) == word.charAt(i) ||
                    word.charAt(i) == '.') {
                    i++;
                } else {
                    break;
                }
            }
            if (i == w.length()) {
                return true;
            }
        }
        return false;
    }
}

class WordDictionary {
public:
    vector<string> store;

    WordDictionary() {}

    void addWord(string word) {
        store.push_back(word);
    }

    bool search(string word) {
        for (string w : store) {
            if (w.length() != word.length()) continue;
            int i = 0;
            while (i < w.length()) {
                if (w[i] == word[i] || word[i] == '.') {
                    i++;
                } else {
                    break;
                }
            }
            if (i == w.length()) {
                return true;
            }
        }
        return false;
    }
};

class WordDictionary {
    constructor() {
        this.store = [];
    }

    /**
     * @param {string} word
     * @return {void}
     */
    addWord(word) {
        this.store.push(word);
    }

    /**
     * @param {string} word
     * @return {boolean}
     */
    search(word) {
        for (let w of this.store) {
            if (w.length !== word.length) continue;
            let i = 0;
            while (i < w.length) {
                if (w[i] === word[i] || word[i] === '.') {
                    i++;
                } else {
                    break;
                }
            }
            if (i === w.length) {
                return true;
            }
        }
        return false;
    }
}

public class WordDictionary {

    private List<string> store;

    public WordDictionary() {
        store = new List<string>();
    }

    public void AddWord(string word) {
        store.Add(word);
    }

    public bool Search(string word) {
        foreach (string w in store) {
            if (w.Length != word.Length) continue;
            int i = 0;
            while (i < w.Length) {
                if (w[i] == word[i] || word[i] == '.') {
                    i++;
                } else {
                    break;
                }
            }
            if (i == w.Length) {
                return true;
            }
        }
        return false;
    }
}

type WordDictionary struct {
	store []string
}

func Constructor() WordDictionary {
	return WordDictionary{store: []string{}}
}

func (this *WordDictionary) AddWord(word string) {
	this.store = append(this.store, word)
}

func (this *WordDictionary) Search(word string) bool {
	for _, w := range this.store {
		if len(w) != len(word) {
			continue
		}
		match := true
		for i := 0; i < len(w); i++ {
			if w[i] != word[i] && word[i] != '.' {
				match = false
				break
			}
		}
		if match {
			return true
		}
	}
	return false
}

class WordDictionary {

    private val store = mutableListOf<String>()

    fun addWord(word: String) {
        store.add(word)
    }

    fun search(word: String): Boolean {
        for (w in store) {
            if (w.length != word.length) continue
            var match = true
            for (i in w.indices) {
                if (w[i] != word[i] && word[i] != '.') {
                    match = false
                    break
                }
            }
            if (match) return true
        }
        return false
    }
}

class WordDictionary {
    private var store: [String]

    init() {
        self.store = []
    }

    func addWord(_ word: String) {
        store.append(word)
    }

    func search(_ word: String) -> Bool {
        for w in store {
            if w.count != word.count {
                continue
            }
            var i = 0
            let wArray = Array(w)
            let wordArray = Array(word)
            while i < wArray.count {
                if wArray[i] == wordArray[i] || wordArray[i] == "." {
                    i += 1
                } else {
                    break
                }
            }
            if i == wArray.count {
                return true
            }
        }
        return false
    }
}

struct WordDictionary {
    store: Vec<String>,
}

impl WordDictionary {
    fn new() -> Self {
        WordDictionary { store: Vec::new() }
    }

    fn add_word(&mut self, word: String) {
        self.store.push(word);
    }

    fn search(&self, word: String) -> bool {
        let word_bytes = word.as_bytes();
        for w in &self.store {
            let w_bytes = w.as_bytes();
            if w_bytes.len() != word_bytes.len() {
                continue;
            }
            let mut i = 0;
            while i < w_bytes.len() {
                if w_bytes[i] == word_bytes[i] || word_bytes[i] == b'.' {
                    i += 1;
                } else {
                    break;
                }
            }
            if i == w_bytes.len() {
                return true;
            }
        }
        false
    }
}

Time & Space Complexity

Time complexity: $O(1)$ for $addWord()$ , $O(m * n)$ for $search()$ .
Space complexity: $O(m * n)$

Where $m$ is the number of words added and $n$ is the length of the string.

2. Depth First Search (Trie)

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = False


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

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

    def search(self, word: str) -> bool:
        def dfs(j, root):
            cur = root

            for i in range(j, len(word)):
                c = word[i]
                if c == ".":
                    for child in cur.children.values():
                        if dfs(i + 1, child):
                            return True
                    return False
                else:
                    if c not in cur.children:
                        return False
                    cur = cur.children[c]
            return cur.word

        return dfs(0, self.root)

public class TrieNode {

    TrieNode[] children;
    boolean word;

    public TrieNode() {
        children = new TrieNode[26];
        word = false;
    }
}

public class WordDictionary {

    private TrieNode root;

    public WordDictionary() {
        root = new TrieNode();
    }

    public void addWord(String word) {
        TrieNode cur = root;
        for (char c : word.toCharArray()) {
            if (cur.children[c - 'a'] == null) {
                cur.children[c - 'a'] = new TrieNode();
            }
            cur = cur.children[c - 'a'];
        }
        cur.word = true;
    }

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

    private boolean dfs(String word, int j, TrieNode root) {
        TrieNode cur = root;

        for (int i = j; i < word.length(); i++) {
            char c = word.charAt(i);
            if (c == '.') {
                for (TrieNode child : cur.children) {
                    if (child != null && dfs(word, i + 1, child)) {
                        return true;
                    }
                }
                return false;
            } else {
                if (cur.children[c - 'a'] == null) {
                    return false;
                }
                cur = cur.children[c - 'a'];
            }
        }
        return cur.word;
    }
}

class TrieNode {
public:
    vector<TrieNode*> children;
    bool word;

    TrieNode() : children(26, nullptr), word(false) {}
};

class WordDictionary {
public:
    TrieNode* root;

    WordDictionary() : root(new TrieNode()) {}

    void addWord(string word) {
        TrieNode* cur = root;
        for (char c : word) {
            if (cur->children[c - 'a'] == nullptr) {
                cur->children[c - 'a'] = new TrieNode();
            }
            cur = cur->children[c - 'a'];
        }
        cur->word = true;
    }

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

private:
    bool dfs(string word, int j, TrieNode* root) {
        TrieNode* cur = root;

        for (int i = j; i < word.size(); i++) {
            char c = word[i];
            if (c == '.') {
                for (TrieNode* child : cur->children) {
                    if (child != nullptr && dfs(word, i + 1, child)) {
                        return true;
                    }
                }
                return false;
            } else {
                if (cur->children[c - 'a'] == nullptr) {
                    return false;
                }
                cur = cur->children[c - 'a'];
            }
        }
        return cur->word;
    }
};

class TrieNode {
    constructor() {
        this.children = Array(26).fill(null);
        this.word = false;
    }
}

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

    /**
     * @param {string} c
     * @return {number}
     */
    getIndex(c) {
        return c.charCodeAt(0) - 'a'.charCodeAt(0);
    }

    /**
     * @param {string} word
     * @return {void}
     */
    addWord(word) {
        let cur = this.root;
        for (const c of word) {
            const idx = this.getIndex(c);
            if (cur.children[idx] === null) {
                cur.children[idx] = new TrieNode();
            }
            cur = cur.children[idx];
        }
        cur.word = true;
    }

    /**
     * @param {string} word
     * @return {boolean}
     */
    search(word) {
        return this.dfs(word, 0, this.root);
    }

    /**
     * @param {string} word
     * @param {number} j
     * @param {TrieNode} root
     * @return {boolean}
     */
    dfs(word, j, root) {
        let cur = root;

        for (let i = j; i < word.length; i++) {
            const c = word[i];
            if (c === '.') {
                for (const child of cur.children) {
                    if (child !== null && this.dfs(word, i + 1, child)) {
                        return true;
                    }
                }
                return false;
            } else {
                const idx = this.getIndex(c);
                if (cur.children[idx] === null) {
                    return false;
                }
                cur = cur.children[idx];
            }
        }
        return cur.word;
    }
}

public class TrieNode {
    public TrieNode[] children = new TrieNode[26];
    public bool word = false;
}

public class WordDictionary {

    private TrieNode root;

    public WordDictionary() {
        root = new TrieNode();
    }

    public void AddWord(string word) {
        TrieNode cur = root;
        foreach (char c in word) {
            if (cur.children[c - 'a'] == null) {
                cur.children[c - 'a'] = new TrieNode();
            }
            cur = cur.children[c - 'a'];
        }
        cur.word = true;
    }

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

    private bool Dfs(string word, int j, TrieNode root) {
        TrieNode cur = root;

        for (int i = j; i < word.Length; i++) {
            char c = word[i];
            if (c == '.') {
                foreach (TrieNode child in cur.children) {
                    if (child != null && Dfs(word, i + 1, child)) {
                        return true;
                    }
                }
                return false;
            } else {
                if (cur.children[c - 'a'] == null) {
                    return false;
                }
                cur = cur.children[c - 'a'];
            }
        }
        return cur.word;
    }
}

type TrieNode struct {
	children [26]*TrieNode
	word     bool
}

func NewTrieNode() *TrieNode {
	return &TrieNode{}
}

type WordDictionary struct {
	root *TrieNode
}

func Constructor() WordDictionary {
	return WordDictionary{root: NewTrieNode()}
}

func (this *WordDictionary) AddWord(word string) {
	cur := this.root
	for _, c := range word {
		index := c - 'a'
		if cur.children[index] == nil {
			cur.children[index] = NewTrieNode()
		}
		cur = cur.children[index]
	}
	cur.word = true
}

func (this *WordDictionary) Search(word string) bool {
	return this.dfs(word, 0, this.root)
}

func (this *WordDictionary) dfs(word string, j int, root *TrieNode) bool {
	cur := root
	for i := j; i < len(word); i++ {
		c := word[i]
		if c == '.' {
			for _, child := range cur.children {
				if child != nil && this.dfs(word, i+1, child) {
					return true
				}
			}
			return false
		} else {
			index := c - 'a'
			if cur.children[index] == nil {
				return false
			}
			cur = cur.children[index]
		}
	}
	return cur.word
}

class TrieNode {
    val children = Array<TrieNode?>(26) { null }
    var word: Boolean = false
}

class WordDictionary {

    private val root = TrieNode()

    fun addWord(word: String) {
        var cur = root
        for (c in word) {
            val index = c - 'a'
            if (cur.children[index] == null) {
                cur.children[index] = TrieNode()
            }
            cur = cur.children[index]!!
        }
        cur.word = true
    }

    fun search(word: String): Boolean {
        return dfs(word, 0, root)
    }

    private fun dfs(word: String, j: Int, root: TrieNode): Boolean {
        var cur = root
        for (i in j until word.length) {
            val c = word[i]
            if (c == '.') {
                for (child in cur.children) {
                    if (child != null && dfs(word, i + 1, child)) {
                        return true
                    }
                }
                return false
            } else {
                val index = c - 'a'
                if (cur.children[index] == null) {
                    return false
                }
                cur = cur.children[index]!!
            }
        }
        return cur.word
    }
}

class TrieNode {
    var children: [Character: TrieNode]
    var word: Bool

    init() {
        self.children = [:]
        self.word = false
    }
}

class WordDictionary {
    private let root: TrieNode

    init() {
        self.root = TrieNode()
    }

    func addWord(_ word: String) {
        var cur = root
        for c in word {
            if cur.children[c] == nil {
                cur.children[c] = TrieNode()
            }
            cur = cur.children[c]!
        }
        cur.word = true
    }

    func search(_ word: String) -> Bool {
        func dfs(_ j: Int, _ root: TrieNode) -> Bool {
            var cur = root
            let wordArray = Array(word)

            for i in j..<wordArray.count {
                let c = wordArray[i]
                if c == "." {
                    for child in cur.children.values {
                        if dfs(i + 1, child) {
                            return true
                        }
                    }
                    return false
                } else {
                    if cur.children[c] == nil {
                        return false
                    }
                    cur = cur.children[c]!
                }
            }
            return cur.word
        }

        return dfs(0, root)
    }
}

struct TrieNode {
    children: [Option<Box<TrieNode>>; 26],
    word: bool,
}

impl TrieNode {
    fn new() -> Self {
        TrieNode {
            children: Default::default(),
            word: false,
        }
    }
}

struct WordDictionary {
    root: TrieNode,
}

impl WordDictionary {
    fn new() -> Self {
        WordDictionary {
            root: TrieNode::new(),
        }
    }

    fn add_word(&mut self, word: String) {
        let mut cur = &mut self.root;
        for c in word.bytes() {
            let idx = (c - b'a') as usize;
            cur = cur.children[idx].get_or_insert_with(|| Box::new(TrieNode::new()));
        }
        cur.word = true;
    }

    fn search(&self, word: String) -> bool {
        Self::dfs(word.as_bytes(), 0, &self.root)
    }

    fn dfs(word: &[u8], j: usize, root: &TrieNode) -> bool {
        let mut cur = root;
        for i in j..word.len() {
            let c = word[i];
            if c == b'.' {
                for child in &cur.children {
                    if let Some(node) = child {
                        if Self::dfs(word, i + 1, node) {
                            return true;
                        }
                    }
                }
                return false;
            } else {
                let idx = (c - b'a') as usize;
                match &cur.children[idx] {
                    None => return false,
                    Some(node) => cur = node,
                }
            }
        }
        cur.word
    }
}

Time & Space Complexity

Time complexity: $O(n)$ for $addWord()$ , $O(n)$ for $search()$ .
Space complexity: $O(t + n)$

Where $n$ is the length of the string and $t$ is the total number of TrieNodes created in the Trie.

Common Pitfalls

Returning True at Any Node Instead of Word-End Nodes

When the search reaches the end of the pattern, you must check if the current node marks the end of a valid word, not just that the node exists. A prefix match is not the same as a word match.

# Wrong - returns True for any prefix match
def dfs(j, root):
    # ... traversal logic ...
    return True  # Incorrect: "app" would match if "apple" was added

# Correct - check if current node is end of word
def dfs(j, root):
    # ... traversal logic ...
    return cur.word  # Only True if a complete word ends here

Not Exploring All Children for Wildcard

When encountering a . wildcard, you must try all possible children nodes. A common mistake is returning after the first child or not iterating through all 26 possible characters.

# Wrong - only checks first child
if c == ".":
    if cur.children and dfs(i + 1, list(cur.children.values())[0]):
        return True

# Correct - must try ALL children
if c == ".":
    for child in cur.children.values():
        if dfs(i + 1, child):
            return True
    return False

Confusing Node Existence with Word Existence

When a character is not found in the Trie, return False immediately. However, when using wildcards, absence of any children should also return False, but only after checking all possibilities.

# Pattern: handle missing paths correctly
if c == ".":
    for child in cur.children.values():
        if child is not None and dfs(i + 1, child):
            return True
    return False  # No valid path found
else:
    if c not in cur.children:
        return False  # Character path doesn't exist
    cur = cur.children[c]