C++实现LeetCode 211.添加和查找单词

Leo

发布时间：2026-10-16 | 6人浏览过

原创

本文介绍如何使用 C++ 在 LeetCode 第 211 题中构建支持添加单词与带通配符 '.' 搜索的数据结构。核心方案采用 Trie（前缀树），利用深度优先搜索递归遍历节点，高效实现精准匹配与模糊搜索功能。

题目解析与思路

本题要求设计一个数据结构，支持两种操作：

void addWord(word)：向结构中添加一个由小写字母组成的单词。
bool search(word)：搜索单词，支持字母 a-z 以及通配符 .。. 可以代表任意一个小写字母。

例如：addWord("bad")，search(".ad") 应返回 true，因为 . 可以匹配 b；而 search("pad") 则返回 false。

解决此问题的基础是建立 Trie（字典树）。在前缀树的结构中，每个节点代表一个字符路径。主要难点在于 search 函数需要处理 . 通配符，这意味着遇到该符号时不能简单跳转下一个固定子节点，而是必须递归检查当前节点的所有非空子树。只要其中一条路径能匹配到单词末尾，即视为搜索成功，这符合典型的深度优先搜索（DFS）模式。

第1步：定义字典树节点类

首先需要在 WordDictionary 中定义内部结构体 TrieNode。每个节点包含：

TrieNode *child[26]：指向26个小写字母的指针数组，用于表示子节点。初始化为 NULL。
bool isWord：标记以该节点为终点的路径是否构成一个完整单词。

构造函数将 isWord 设为 false 并清空子指针数组。同时创建根节点 root 作为插入操作的起始点。

第2步：实现单词添加逻辑 addWord

addWord 负责构建或扩展前缀树：

入口：从根节点 root 开始遍历。
动作：逐个读取单词中的字符，计算其对应的索引（char - 'a'）。如果当前节点的对应子指针为空，则新建一个 TrieNode；否则直接移动到该子节点。
完成状态：当单词遍历完毕到达最后一个字符对应的节点时，将该节点的 isWord 属性设为 true。

此步骤确保了单词能够按字符序列精确地存储在树的分支上。

第3步：实现含通配符的搜索逻辑 search

搜索过程涉及两个函数：公共接口 search 和私有递归辅助函数 searchWord。

公共接口：调用 searchWord(word, root, 0)，传入完整单词、当前节点和初始索引 0。

递归判断：

基准条件：如果索引 i 等于单词长度，说明已检查完所有字符，此时仅当当前节点的 isWord 为 true 时才返回 true。
通配符处理：若当前字符是 '.'，则需要尝试当前节点的所有26个子节点。遍历 p->child 数组，跳过空指针，对每个有效子节点发起新的 searchWord 调用（索引 +1）。若任一调用返回 true，整体即刻返回 true；若循环结束仍未找到，返回 false。
普通字符处理：若非通配符，计算目标子索引。若该子节点存在且后续递归调用返回 true，则返回 true；否则返回 false。

这种设计保证了 . 能够灵活匹配任何单一字母，同时维持了前缀树的高效性。

代码参考

以下是完整的 C++ 实现，包含了上述逻辑的核心结构：

class WordDictionary {
public:
    struct TrieNode {
        TrieNode *child[26];
        bool isWord;
        TrieNode() : isWord(false) {
            for (auto &a : child) a = NULL;
        }
    };
    
    WordDictionary() {
        root = new TrieNode();
    }
    
    void addWord(string word) {
        TrieNode *p = root;
        for (auto &a : word) {
            int i = a - 'a';
            if (!p->child[i]) p->child[i] = new TrieNode();
            p = p->child[i];
        }
        p->isWord = true;
    }

    bool search(string word) {
        return searchWord(word, root, 0);
    }
    
    bool searchWord(string &word, TrieNode *p, int i) {
        if (i == word.size()) return p->isWord;
        if (word[i] == '.') {
            for (auto &a : p->child) {
                if (a && searchWord(word, a, i + 1)) return true;
            }
            return false;
        } else {
            return p->child[word[i] - 'a'] && searchWord(word, p->child[word[i] - 'a'], i + 1);
        }
    }
    
private:
    TrieNode *root;
};

以上就是使用C++实现LeetCode 211题添加和查找单词数据结构的详细内容，更多关于C++实现添加和查找单词-数据结构设计的资料请关注本站其它相关文章！