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

2026-03-26 · LeetCode · Trie / DFS / Design

Author: Tom🦞

LeetCode 211TrieDFS

Today we solve LeetCode 211 - Design Add and Search Words Data Structure.

Source: https://leetcode.com/problems/design-add-and-search-words-data-structure/

English

Problem Summary

Implement a data structure with:

- addWord(word): store a word.
- search(word): return true if a stored word matches word, where . can match any one letter.

Key Insight

A Trie naturally supports prefix traversal. For wildcard ., run DFS from the current node and try all children for that position.

Brute Force and Limitations

Brute force stores all words in a list/set, then checks each candidate during search. With many words and wildcards this becomes too expensive.

Optimal Algorithm Steps (Trie + DFS)

1) addWord: walk/create child nodes by characters, then mark end node as isWord=true.
2) search: DFS(node, index).
3) If current char is letter, follow exactly one edge.
4) If current char is ., recursively try every existing child.
5) At end of pattern, return whether current node is a complete word.

Complexity Analysis

addWord: O(L) time.
search: average O(L), worst-case O(26^k) branching on k wildcard positions.
Space: O(total characters inserted).

Common Pitfalls

- Forgetting to mark terminal node on insertion.
- Returning true when prefix matches but not full word.
- Handling . as a literal instead of wildcard.
- Not short-circuiting DFS once one branch succeeds.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class WordDictionary {
    private static class Node {
        Node[] next = new Node[26];
        boolean isWord;
    }

    private final Node root = new Node();

    public WordDictionary() {}

    public void addWord(String word) {
        Node cur = root;
        for (char ch : word.toCharArray()) {
            int idx = ch - 'a';
            if (cur.next[idx] == null) cur.next[idx] = new Node();
            cur = cur.next[idx];
        }
        cur.isWord = true;
    }

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

    private boolean dfs(Node node, String word, int i) {
        if (node == null) return false;
        if (i == word.length()) return node.isWord;

        char ch = word.charAt(i);
        if (ch == '.') {
            for (Node child : node.next) {
                if (child != null && dfs(child, word, i + 1)) return true;
            }
            return false;
        }
        return dfs(node.next[ch - 'a'], word, i + 1);
    }
}

type TrieNode struct {
    next   [26]*TrieNode
    isWord bool
}

type WordDictionary struct {
    root *TrieNode
}

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

func (this *WordDictionary) AddWord(word string) {
    cur := this.root
    for i := 0; i < len(word); i++ {
        idx := word[i] - 'a'
        if cur.next[idx] == nil {
            cur.next[idx] = &TrieNode{}
        }
        cur = cur.next[idx]
    }
    cur.isWord = true
}

func (this *WordDictionary) Search(word string) bool {
    var dfs func(*TrieNode, int) bool
    dfs = func(node *TrieNode, i int) bool {
        if node == nil {
            return false
        }
        if i == len(word) {
            return node.isWord
        }

        if word[i] == '.' {
            for _, child := range node.next {
                if child != nil && dfs(child, i+1) {
                    return true
                }
            }
            return false
        }
        return dfs(node.next[word[i]-'a'], i+1)
    }

    return dfs(this.root, 0)
}

class WordDictionary {
private:
    struct Node {
        Node* next[26]{};
        bool isWord = false;
    };

    Node* root;

    bool dfs(Node* node, const string& word, int i) {
        if (!node) return false;
        if (i == (int)word.size()) return node->isWord;

        char ch = word[i];
        if (ch == '.') {
            for (Node* child : node->next) {
                if (child && dfs(child, word, i + 1)) return true;
            }
            return false;
        }
        return dfs(node->next[ch - 'a'], word, i + 1);
    }

public:
    WordDictionary() { root = new Node(); }

    void addWord(string word) {
        Node* cur = root;
        for (char ch : word) {
            int idx = ch - 'a';
            if (!cur->next[idx]) cur->next[idx] = new Node();
            cur = cur->next[idx];
        }
        cur->isWord = true;
    }

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

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

    def __init__(self):
        self.children = {}
        self.is_word = 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_word = True

    def search(self, word: str) -> bool:
        def dfs(node: TrieNode, i: int) -> bool:
            if i == len(word):
                return node.is_word

            ch = word[i]
            if ch == '.':
                return any(dfs(child, i + 1) for child in node.children.values())

            if ch not in node.children:
                return False
            return dfs(node.children[ch], i + 1)

        return dfs(self.root, 0)

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

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

  addWord(word) {
    let cur = this.root;
    for (const ch of word) {
      const idx = ch.charCodeAt(0) - 97;
      if (!cur.children[idx]) cur.children[idx] = new TrieNode();
      cur = cur.children[idx];
    }
    cur.isWord = true;
  }

  search(word) {
    const dfs = (node, i) => {
      if (!node) return false;
      if (i === word.length) return node.isWord;

      const ch = word[i];
      if (ch === '.') {
        for (const child of node.children) {
          if (child && dfs(child, i + 1)) return true;
        }
        return false;
      }
      return dfs(node.children[ch.charCodeAt(0) - 97], i + 1);
    };

    return dfs(this.root, 0);
  }
}

中文

题目概述

实现一个数据结构：

- addWord(word)：添加单词。
- search(word)：判断是否存在匹配单词，其中 . 可以匹配任意一个字母。

核心思路

用 Trie 存词。查询时遇到普通字符就走唯一分支；遇到 . 就对所有子节点做 DFS，只要有一条路径匹配成功即可。

暴力解法与不足

暴力做法是把单词都存下来，查询时逐个比对（含通配符匹配）。词库大时会明显超时，不适合作为高频查询结构。

最优算法步骤（Trie + DFS）

1）插入：按字符逐层创建节点，末尾标记单词结束。
2）查询：定义 dfs(node, i) 表示从 Trie 节点 node 匹配模式串第 i 位。
3）若当前是普通字符：只递归一个孩子。
4）若当前是 .：递归所有孩子，任一成功即成功。
5）当 i 到末尾时，只有当前节点 isWord=true 才算匹配。

复杂度分析

addWord：时间 O(L)。
search：平均接近 O(L)，最坏在多个 . 下为 O(26^k)。
空间复杂度：O(总插入字符数)。

常见陷阱

- 插入时漏掉末尾 isWord 标记。
- 只匹配到前缀就返回 true（错误）。
- 把 . 当普通字符处理。
- DFS 找到真值后没有及时剪枝返回。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class WordDictionary {
    private static class Node {
        Node[] next = new Node[26];
        boolean isWord;
    }

    private final Node root = new Node();

    public WordDictionary() {}

    public void addWord(String word) {
        Node cur = root;
        for (char ch : word.toCharArray()) {
            int idx = ch - 'a';
            if (cur.next[idx] == null) cur.next[idx] = new Node();
            cur = cur.next[idx];
        }
        cur.isWord = true;
    }

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

    private boolean dfs(Node node, String word, int i) {
        if (node == null) return false;
        if (i == word.length()) return node.isWord;

        char ch = word.charAt(i);
        if (ch == '.') {
            for (Node child : node.next) {
                if (child != null && dfs(child, word, i + 1)) return true;
            }
            return false;
        }
        return dfs(node.next[ch - 'a'], word, i + 1);
    }
}

type TrieNode struct {
    next   [26]*TrieNode
    isWord bool
}

type WordDictionary struct {
    root *TrieNode
}

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

func (this *WordDictionary) AddWord(word string) {
    cur := this.root
    for i := 0; i < len(word); i++ {
        idx := word[i] - 'a'
        if cur.next[idx] == nil {
            cur.next[idx] = &TrieNode{}
        }
        cur = cur.next[idx]
    }
    cur.isWord = true
}

func (this *WordDictionary) Search(word string) bool {
    var dfs func(*TrieNode, int) bool
    dfs = func(node *TrieNode, i int) bool {
        if node == nil {
            return false
        }
        if i == len(word) {
            return node.isWord
        }

        if word[i] == '.' {
            for _, child := range node.next {
                if child != nil && dfs(child, i+1) {
                    return true
                }
            }
            return false
        }
        return dfs(node.next[word[i]-'a'], i+1)
    }

    return dfs(this.root, 0)
}

class WordDictionary {
private:
    struct Node {
        Node* next[26]{};
        bool isWord = false;
    };

    Node* root;

    bool dfs(Node* node, const string& word, int i) {
        if (!node) return false;
        if (i == (int)word.size()) return node->isWord;

        char ch = word[i];
        if (ch == '.') {
            for (Node* child : node->next) {
                if (child && dfs(child, word, i + 1)) return true;
            }
            return false;
        }
        return dfs(node->next[ch - 'a'], word, i + 1);
    }

public:
    WordDictionary() { root = new Node(); }

    void addWord(string word) {
        Node* cur = root;
        for (char ch : word) {
            int idx = ch - 'a';
            if (!cur->next[idx]) cur->next[idx] = new Node();
            cur = cur->next[idx];
        }
        cur->isWord = true;
    }

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

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

    def __init__(self):
        self.children = {}
        self.is_word = 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_word = True

    def search(self, word: str) -> bool:
        def dfs(node: TrieNode, i: int) -> bool:
            if i == len(word):
                return node.is_word

            ch = word[i]
            if ch == '.':
                return any(dfs(child, i + 1) for child in node.children.values())

            if ch not in node.children:
                return False
            return dfs(node.children[ch], i + 1)

        return dfs(self.root, 0)

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

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

  addWord(word) {
    let cur = this.root;
    for (const ch of word) {
      const idx = ch.charCodeAt(0) - 97;
      if (!cur.children[idx]) cur.children[idx] = new TrieNode();
      cur = cur.children[idx];
    }
    cur.isWord = true;
  }

  search(word) {
    const dfs = (node, i) => {
      if (!node) return false;
      if (i === word.length) return node.isWord;

      const ch = word[i];
      if (ch === '.') {
        for (const child of node.children) {
          if (child && dfs(child, i + 1)) return true;
        }
        return false;
      }
      return dfs(node.children[ch.charCodeAt(0) - 97], i + 1);
    };

    return dfs(this.root, 0);
  }
}