211. Design Add and Search Words Data Structure (Medium)

Problem

Design a data structure supporting:

addWord(word), add a word.
search(word), true iff any added word matches. word may contain . which matches any single letter.

Example

wd = WordDictionary();
wd.addWord("bad"); wd.addWord("dad"); wd.addWord("mad");
wd.search("pad");  // false
wd.search("bad");  // true
wd.search(".ad");  // true
wd.search("b..");  // true

LeetCode 211 · Link · Medium

Try it yourself

Python
Go

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, list of words, regex match

Store words in a list; on search, compile . as a regex pattern and scan every word.

import re

class WordDictionary:
    def __init__(self):
        self.words = []

    def addWord(self, word):
        self.words.append(word)          # L1: O(1) list append

    def search(self, word):
        pattern = re.compile("^" + word + "$")   # L2: O(L) compile regex
        return any(pattern.match(w) for w in self.words)  # L3: O(W · L) scan

class WordDictionary {
    private words: string[] = [];

    addWord(word: string): void {
        this.words.push(word);                      // L1: O(1) push
    }

    search(word: string): boolean {
        const pattern = new RegExp("^" + word.replace(/\./g, ".") + "$");  // L2: O(L) compile
        return this.words.some(w => pattern.test(w));  // L3: O(W · L) scan
    }
}

package main

import (
    "fmt"
    "regexp"
)

type WordDictionary struct {
    words []string
}

func NewWordDictionary() *WordDictionary { return &WordDictionary{} }

func (wd *WordDictionary) AddWord(word string) {
    wd.words = append(wd.words, word)           // L1: O(1) amortized append
}

func (wd *WordDictionary) Search(word string) bool {
    pattern := regexp.MustCompile("^" + word + "$") // L2: O(L) compile
    for _, w := range wd.words {
        if pattern.MatchString(w) {             // L3: O(W · L) scan
            return true
        }
    }
    return false
}

func runTests() {
    wd := NewWordDictionary()
    wd.AddWord("bad"); wd.AddWord("dad"); wd.AddWord("mad")
    fmt.Println(wd.Search("pad"), wd.Search("bad"), wd.Search(".ad"))
}

func main() { runTests() }

final class WordDictionary {
    private var words: [String] = []
    init() {}
    func addWord(_ word: String) { words.append(word) }
    func search(_ word: String) -> Bool {
        let pattern = Array(word)
        return words.contains { candidate in
            let characters = Array(candidate)
            return characters.count == pattern.count && characters.indices.allSatisfy {
                pattern[$0] == "." || pattern[$0] == characters[$0]
            }
        }
    }
}

Where the time goes, line by line

Variables: L = len(word), W = total words added.

Line	Per-call cost	Times executed	Contribution
L1 (addWord)	$O(1)$	1 per call	$O(1)$ per addWord
L2 (compile)	$O(L)$	1 per search	$O(L)$
L3 (scan + match)	$O(L)$	W	$O(W · L)$ per search ← dominates

Complexity

addWord: $O(1)$ .
search: $O(W · L)$ , driven by L3 (scanning all words). Degrades as words accumulate.
Space: $O(total chars)$ .

Approach 2: Hash map bucketed by length + per-position scan

Group words by length; on search, compare character-by-character only against same-length words. Faster pruning but still linear in group size.

from collections import defaultdict

class WordDictionary:
    def __init__(self):
        self.by_len = defaultdict(list)

    def addWord(self, word):
        self.by_len[len(word)].append(word)  # L1: O(1) amortized append

    def search(self, word):
        for w in self.by_len.get(len(word), []):   # L2: scan same-length words, O(W_L)
            if all(p == '.' or p == c for p, c in zip(word, w)):  # L3: O(L) char compare
                return True
        return False

class WordDictionary {
    private byLen: Map<number, string[]> = new Map();

    addWord(word: string): void {
        if (!this.byLen.has(word.length)) this.byLen.set(word.length, []);
        this.byLen.get(word.length)!.push(word);  // L1: O(1) amortized push
    }

    search(word: string): boolean {
        const candidates = this.byLen.get(word.length) ?? [];
        for (const w of candidates) {             // L2: scan same-length words, O(W_L)
            let match = true;
            for (let i = 0; i < word.length; i++) {
                if (word[i] !== '.' && word[i] !== w[i]) { match = false; break; }  // L3: O(L) char compare
            }
            if (match) return true;
        }
        return false;
    }
}

package main

import "fmt"

type WordDictionary struct {
    byLen map[int][]string
}

func NewWordDictionary() *WordDictionary {
    return &WordDictionary{byLen: make(map[int][]string)}
}

func (wd *WordDictionary) AddWord(word string) {
    wd.byLen[len(word)] = append(wd.byLen[len(word)], word) // L1: O(1) amortized append
}

func (wd *WordDictionary) Search(word string) bool {
    for _, w := range wd.byLen[len(word)] {             // L2: scan same-length words, O(W_L)
        match := true
        for i := 0; i < len(word); i++ {
            if word[i] != '.' && word[i] != w[i] {     // L3: O(L) char compare
                match = false
                break
            }
        }
        if match {
            return true
        }
    }
    return false
}

func assert(condition bool, msgs ...string) {
    if !condition {
        msg := "assertion failed"
        if len(msgs) > 0 { msg = msgs[0] }
        panic(msg)
    }
}

func runTests() {
    wd := NewWordDictionary()
    wd.AddWord("bad"); wd.AddWord("dad"); wd.AddWord("mad")
    assert(wd.Search("pad") == false)
    assert(wd.Search("bad") == true)
    assert(wd.Search(".ad") == true)
    assert(wd.Search("b..") == true)
    assert(wd.Search("...") == true)
    assert(wd.Search("....") == false)
    fmt.Println("all tests pass")
}

func main() { runTests() }

final class WordDictionary {
    private var wordsByLength: [Int: [[Character]]] = [:]
    init() {}
    func addWord(_ word: String) { wordsByLength[word.count, default: []].append(Array(word)) }
    func search(_ word: String) -> Bool {
        let pattern = Array(word)
        return wordsByLength[pattern.count, default: []].contains { candidate in
            candidate.indices.allSatisfy { pattern[$0] == "." || pattern[$0] == candidate[$0] }
        }
    }
}

Where the time goes, line by line

Variables: L = len(word), W_L = number of stored words of length L.

Line	Per-call cost	Times executed	Contribution
L1 (addWord)	$O(1)$ amortized	1 per call	$O(1)$ per addWord
L2 (group scan)	$O(1)$	W_L	$O(W_L)$
L3 (char compare)	$O(L)$	W_L	$O(W_L · L)$ per search ← dominates

Bucketing by length prunes same-length candidates immediately, but within the bucket we still scan linearly.

Complexity

addWord: $O(L)$ , driven by hashing the length key.
search: $O(W_L · L)$ , driven by L3 (per-word character comparison within the same-length bucket).

Reasonable for small L and small W_L.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Trie with DFS wildcard (canonical)

Store words in a trie. On search, follow the trie character by character; for ., branch to every child via DFS.

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

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

    def addWord(self, word):
        node = self.root
        for ch in word:                            # L1: iterate L characters
            if ch not in node.children:
                node.children[ch] = TrieNode()    # L2: O(1) create node
            node = node.children[ch]              # L3: O(1) descend
        node.is_end = True                        # L4: O(1) mark end

    def search(self, word):
        def dfs(i, node):
            if i == len(word):                    # L5: base case
                return node.is_end
            ch = word[i]
            if ch == '.':                         # L6: wildcard: try all children
                return any(dfs(i + 1, child) for child in node.children.values())  # L7: up to 26 branches
            if ch in node.children:               # L8: O(1) exact match
                return dfs(i + 1, node.children[ch])  # L9: recurse one path
            return False
        return dfs(0, self.root)

class TrieNode {
    children: Map<string, TrieNode> = new Map();
    isEnd: boolean = false;
}

class WordDictionary {
    private root = new TrieNode();

    addWord(word: string): void {
        let node = this.root;
        for (const ch of word) {                          // L1: iterate L characters
            if (!node.children.has(ch)) node.children.set(ch, new TrieNode());  // L2: O(1) create node
            node = node.children.get(ch)!;                // L3: O(1) descend
        }
        node.isEnd = true;                                // L4: O(1) mark end
    }

    search(word: string): boolean {
        return this.dfs(0, this.root, word);
    }

    private dfs(i: number, node: TrieNode, word: string): boolean {
        if (i === word.length) return node.isEnd;         // L5: base case
        const ch = word[i];
        if (ch === '.') {                                 // L6: wildcard: try all children
            for (const child of node.children.values()) {
                if (this.dfs(i + 1, child, word)) return true;  // L7: up to 26 branches
            }
            return false;
        }
        if (!node.children.has(ch)) return false;         // L8: O(1) exact match check
        return this.dfs(i + 1, node.children.get(ch)!, word);  // L9: recurse one path
    }
}

package main

import "fmt"

type TrieNode struct {
    Children [26]*TrieNode
    IsEnd    bool
}

type WordDictionary struct {
    Root *TrieNode
}

func NewWordDictionary() *WordDictionary { return &WordDictionary{Root: &TrieNode{}} }

func (wd *WordDictionary) AddWord(word string) {
    node := wd.Root
    for _, ch := range word {                    // L1: iterate L characters
        i := ch - 'a'
        if node.Children[i] == nil {
            node.Children[i] = &TrieNode{}      // L2: O(1) create node
        }
        node = node.Children[i]                 // L3: O(1) descend
    }
    node.IsEnd = true                           // L4: O(1) mark end
}

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

func (wd *WordDictionary) dfs(idx int, node *TrieNode, word string) bool {
    if idx == len(word) {
        return node.IsEnd                       // L5: base case
    }
    ch := word[idx]
    if ch == '.' {                             // L6: wildcard: try all children
        for _, child := range node.Children {
            if child != nil && wd.dfs(idx+1, child, word) { // L7: up to 26 branches
                return true
            }
        }
        return false
    }
    i := ch - 'a'
    if node.Children[i] == nil {
        return false                            // L8: O(1) exact match check
    }
    return wd.dfs(idx+1, node.Children[i], word) // L9: recurse one path
}

func assert(condition bool, msgs ...string) {
    if !condition {
        msg := "assertion failed"
        if len(msgs) > 0 { msg = msgs[0] }
        panic(msg)
    }
}

func runTests() {
    wd := NewWordDictionary()
    wd.AddWord("bad"); wd.AddWord("dad"); wd.AddWord("mad")
    assert(wd.Search("pad") == false)
    assert(wd.Search("bad") == true)
    assert(wd.Search(".ad") == true)
    assert(wd.Search("b..") == true)
    assert(wd.Search("...") == true)
    assert(wd.Search("....") == false)
    fmt.Println("all tests pass")
}

func main() { runTests() }

final class WordDictionary {
    private let root = TrieNode()
    init() {}
    func addWord(_ word: String) {
        var node = root
        for character in word {
            if node.children[character] == nil { node.children[character] = TrieNode() }
            guard let child = node.children[character] else { return }
            node = child
        }
        node.isWord = true
    }
    func search(_ word: String) -> Bool {
        let pattern = Array(word)
        func matches(_ index: Int, _ node: TrieNode) -> Bool {
            if index == pattern.count { return node.isWord }
            let character = pattern[index]
            if character == "." { return node.children.values.contains { matches(index + 1, $0) } }
            guard let child = node.children[character] else { return false }
            return matches(index + 1, child)
        }
        return matches(0, root)
    }
}

Where the time goes, line by line

Variables: L = len(word), k = number of distinct child characters per node (≤ 26).

Line	Per-call cost	Times executed	Contribution
L1-L4 (addWord loop)	$O(1)$ per char	L	$O(L)$ per addWord ← dominates for addWord
L5-L6/L8 (exact match path)	$O(1)$ per level	L levels	$O(L)$ avg search
L7 (wildcard branch)	$O(k)$ per level	up to L levels	$O(k^L)$ worst case ← dominates for all-wildcard

For exact character matches, each DFS call moves one level deeper and is $O(1)$ . For . wildcards, each level branches to up to k = 26 children, giving $O(26^L)$ in the worst case (all wildcards, dense trie).

Complexity

addWord: $O(L)$ , driven by L1-L4.
search: $O(L)$ average (no wildcards), $O(26^L)$ worst (all wildcards in a dense trie).
Space: $O(total chars)$ .

The wildcard branches are where performance can degrade: a query like "......" against a dense dictionary is the pathological case.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	addWord	search	Notes
List + regex	$O(1)$	$O(W · L)$	Naive
Length-bucketed list	$O(L)$	$O(W_L · L)$	Better pruning
Trie + DFS wildcard	$O(L)$	$O(L)$ avg	Canonical

The trie approach generalizes to 212 Word Search II (the next problem) where we DFS a grid against a trie of candidate words.

Test cases

# Quick smoke tests - paste into a REPL or save as test_211.py and run.
# Uses the canonical Approach 3 implementation (trie + DFS wildcard).

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

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

    def addWord(self, word):
        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):
        def dfs(i, node):
            if i == len(word):
                return node.is_end
            ch = word[i]
            if ch == '.':
                return any(dfs(i + 1, child) for child in node.children.values())
            if ch in node.children:
                return dfs(i + 1, node.children[ch])
            return False
        return dfs(0, self.root)

def _run_tests():
    wd = WordDictionary()
    wd.addWord("bad")
    wd.addWord("dad")
    wd.addWord("mad")
    assert wd.search("pad") == False
    assert wd.search("bad") == True
    assert wd.search(".ad") == True     # matches bad, dad, mad
    assert wd.search("b..") == True     # matches bad
    assert wd.search("...") == True     # matches any 3-letter word
    assert wd.search("....") == False   # no 4-letter words
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

class TrieNode {
    children: Map<string, TrieNode> = new Map();
    isEnd: boolean = false;
}

class WordDictionary {
    private root = new TrieNode();
    addWord(word: string): void {
        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;
    }
    search(word: string): boolean {
        return this.dfs(0, this.root, word);
    }
    private dfs(i: number, node: TrieNode, word: string): boolean {
        if (i === word.length) return node.isEnd;
        const ch = word[i];
        if (ch === '.') {
            for (const child of node.children.values()) {
                if (this.dfs(i + 1, child, word)) return true;
            }
            return false;
        }
        if (!node.children.has(ch)) return false;
        return this.dfs(i + 1, node.children.get(ch)!, word);
    }
}

const wd = new WordDictionary();
wd.addWord("bad"); wd.addWord("dad"); wd.addWord("mad");
console.assert(wd.search("pad") === false);
console.assert(wd.search("bad") === true);
console.assert(wd.search(".ad") === true);
console.assert(wd.search("b..") === true);
console.assert(wd.search("...") === true);
console.assert(wd.search("....") === false);
console.log("all tests pass");

package main

import "fmt"

type TrieNode struct {
    Children [26]*TrieNode
    IsEnd    bool
}

type WordDictionary struct{ Root *TrieNode }

func NewWordDictionary() *WordDictionary { return &WordDictionary{Root: &TrieNode{}} }

func (wd *WordDictionary) AddWord(word string) {
    node := wd.Root
    for _, ch := range word {
        i := ch - 'a'
        if node.Children[i] == nil { node.Children[i] = &TrieNode{} }
        node = node.Children[i]
    }
    node.IsEnd = true
}

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

func (wd *WordDictionary) dfs(idx int, node *TrieNode, word string) bool {
    if idx == len(word) { return node.IsEnd }
    ch := word[idx]
    if ch == '.' {
        for _, child := range node.Children {
            if child != nil && wd.dfs(idx+1, child, word) { return true }
        }
        return false
    }
    i := ch - 'a'
    if node.Children[i] == nil { return false }
    return wd.dfs(idx+1, node.Children[i], word)
}

func assert(condition bool, msgs ...string) {
    if !condition {
        msg := "assertion failed"
        if len(msgs) > 0 { msg = msgs[0] }
        panic(msg)
    }
}

func runTests() {
    wd := NewWordDictionary()
    wd.AddWord("bad"); wd.AddWord("dad"); wd.AddWord("mad")
    assert(wd.Search("pad") == false)
    assert(wd.Search("bad") == true)
    assert(wd.Search(".ad") == true)    // matches bad, dad, mad
    assert(wd.Search("b..") == true)    // matches bad
    assert(wd.Search("...") == true)    // matches any 3-letter word
    assert(wd.Search("....") == false)  // no 4-letter words
    fmt.Println("all tests pass")
}

func main() { runTests() }

Tries, trie with wildcard DFS

Trie Prefix Search, the prefix tree model for sharing string prefixes and pruning searches.
DFS, the depth first traversal habit of following one branch before returning.

211. Design Add and Search Words Data Structure (Medium)

Problem

Try it yourself

Approach 1: Brute force, list of words, regex match

Approach 2: Hash map bucketed by length + per-position scan

Approach 3: Trie with DFS wildcard (canonical)

Summary

Test cases

Related data structures

Related concepts