原文链接: https://leetcode-cn.com/problems/design-add-and-search-words-data-structure

英文原文

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

• WordDictionary() Initializes the object.
• void addWord(word) Adds word to the data structure, it can be matched later.
• 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:

Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]

Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

 

Constraints:

• 1 <= word.length <= 500
• word in addWord consists lower-case English letters.
• word in search consist of  '.' or lower-case English letters.
• At most 50000 calls will be made to addWord and search.

中文题目

请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。

实现词典类 WordDictionary ：

• WordDictionary() 初始化词典对象
• void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配
• bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回  false 。word 中可能包含一些 '.' ，每个 . 都可以表示任何一个字母。

 

示例：

输入：
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
输出：
[null,null,null,null,false,true,true,true]

解释：
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

 

提示：

• 1 <= word.length <= 500
• addWord 中的 word 由小写英文字母组成
• search 中的 word 由 '.' 或小写英文字母组成
• 最多调用 50000 次 addWord 和 search

通过代码

高赞题解

各位题友大家好！ 我是 @负雪明烛 。今天力扣上的每日一题是「211. 添加与搜索单词 - 数据结构设计」。

解题思路

本文写成前缀树入门教程。

从二叉树说起

前缀树（Trie，字典树），也是一种树。为了理解前缀树，我们先从「二叉树」说起。

常见的二叉树结构是下面这样的：

class TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
}

可以看到一个树的节点包含了三个元素：该节点本身的值，左子树的指针，右子树的指针。

二叉树可视化是下面这样的：

二叉树的每个节点只有两个孩子，那如果每个节点可以有多个孩子呢？这就形成了「多叉树」。多叉树的子节点数目一般不是固定的，所以会用变长数组来保存所有的子节点的指针。多叉树的结构是下面这样：

class TreeNode {
    int val;
    vector<TreeNode*> children;
}

多叉树可视化是下面这样：

对于普通的多叉树，每个节点的所有子节点可能是没有任何规律的。而本题讨论的「前缀树」就是每个节点的 children 有规律的多叉树。

前缀树

「前缀树」是一种特殊的多叉树，它的 TrieNode 中 chidren 是一个大小为 26 的一维数组（当输入只有小写字符），分别对应了26个英文字符 'a' ~ 'z'，也就是说形成了一棵「26 叉树」。

前缀树的结构可以定义为下面这样：

class TrieNode {
public:
    vector<TrieNode*> children;
    bool isWord;
    TrieNode() : isWord(false), children(26, nullptr) {
    }
    ~TrieNode() {
        for (auto& c : children)
            delete c;
    }
};

​

TrieNode 里面存储了两个信息：

• children 是该节点的所有子节点。
• isWord 表示从根节点到当前节点为止，该路径是否形成了一个有效的字符串。

构建

在构建前缀树的时候，按照下面的方法：

• 根节点不保存任何信息；
• 关键词放到「前缀树」时，需要把它拆成各个字符，每个字符按照其在 'a' ~ 'z' 的序号，放在 chidren 对应的位置里面。下一个字符是当前字符的子节点。
• 一个输入字符串构建「前缀树」结束的时候，需要把该节点的 isWord 标记为 true，说明从根节点到当前节点的路径，构成了一个关键词。

下面是一棵「前缀树」，其中保存了 {"am", "an", "as", "b", "c", "cv"} 这些关键词。图中红色表示 isWord 为 true。

看下面这个图的时候需要注意：

1. 所有以相同字符开头的字符串，会聚合到同一个子树上。比如 {"am", "an", "as"} ；
2. 并不一定是到达叶子节点才形成了一个关键词，只要 isWord 为 true，那么从根节点到当前节点的路径就是关键词。比如 {"c", "cv"} ；

有些题解把字符画在了节点中，我认为是不准确的。因为前缀树是根据 字符在 children 中的位置确定子树，而不真正在树中存储了  'a' ~ 'z' 这些字符。树中每个节点存储的 isWord，表示从根节点到当前节点的路径是否构成了一个关键词。

查询

在判断一个关键词是否在「前缀树」中时，需要依次遍历该关键词所有字符，在前缀树中找出这条路径。可能出现三种情况：

1. 在寻找路径的过程中，发现到某个位置路径断了。比如在上面的前缀树图中寻找 "d" 或者 "ar" 或者 "any" ，由于树中没有构建对应的节点，那么就查找不到这些关键词；
2. 找到了这条路径，但是最后一个节点的 isWord 为 false。这也说明没有该关键词。比如在上面的前缀树图中寻找 "a" ；
3. 找到了这条路径，并且最后一个节点的 isWord 为 true。这说明前缀树存储了这个关键词，比如上面前缀树图中的 "am" , "cv" 等。

应用

上面说了这么多前缀树，那前缀树有什么用呢？

其实我们生活中就有应用。

• 比如我们常见的电话拨号键盘，当我们输入一些数字的时候，后面会自动提示以我们的输入数字为开头的所有号码。
• 比如我们的英文输入法，当我们输入半个单词的时候，输入法上面会自动联想和补全后面可能的单词。
• 再比如在搜索框搜索的时候，输入"负雪"，后面会联想到 负雪明烛 。

等等。

代码

本题是前缀树的变种： '.' 可以表示任何一个小写字符。
​

在匹配的过程中，如果遇到了 '.' ，则需要对当前节点的所有子树都进行遍历，只要有任何一个子树能最终匹配完成，那么就代表能匹配完成。
​

代码中的 match() 函数表示在以 root 为根节点的前缀树中，能不能匹配到 word[index:] 。

下面的 Python 解法和 C++ 解法定义的前缀树略有不同：

• Python 解法中，保存 children 是使用的字典，它保存的结构是 {字符：Node} ，所以可以直接通过 children['a'] 来获取当前节点的 'a' 子树。
• C++ 解法中，保存 children 用的题解分析时讲的大小为 26 的数组实现的。而且我的 C++ 解法中写出了很多人容易忽略的一个细节，就是 TrieNode 析构的时候，需要手动释放内存。

Python / C++ 代码如下：

[]
class Node(object):
    def __init__(self):
        self.children = collections.defaultdict(Node)
        self.isword = False
        
class WordDictionary(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = Node()

    def addWord(self, word):
        """
        Adds a word into the data structure.
        :type word: str
        :rtype: void
        """
        current = self.root
        for w in word:
            current = current.children[w]
        current.isword = True

    def search(self, word):
        """
        Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
        :type word: str
        :rtype: bool
        """
        return self.match(word, 0, self.root)
    
    def match(self, word, index, root):
        if root == None:
            return False
        if index == len(word):
            return root.isword
        if word[index] != '.':
            return root != None and self.match(word, index + 1, root.children.get(word[index]))
        else:
            for child in root.children.values():
                if self.match(word, index + 1, child):
                    return True
        return False

# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)

[]
class TrieNode{
public:
    vector<TrieNode*> child;
    bool isWord;
    TrieNode() : child(26, nullptr), isWord(false) {};
    ~TrieNode() {
        for (auto c : child) delete c;
    }
};
class WordDictionary {
public:
    /** Initialize your data structure here. */
    WordDictionary() {
        root = new TrieNode();
    }
    ~WordDictionary() {
        delete root;
    }
    /** Adds a word into the data structure. */
    void addWord(string word) {
        TrieNode* p = root;
        for (char c : word) {
            int i = c - 'a';
            if (!p->child[i])
                p->child[i] = new TrieNode();
            p = p->child[i];
        }
        p->isWord = true;
    }
    
    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    bool search(string word) {
        return match(word, root, 0);
    }
    
    bool match(string& word, TrieNode* p, int start) {
        if (!p) return false;
        if (start == word.size()) return p->isWord;
        char c = word[start];
        if (c != '.') {
            return match(word, p->child[c - 'a'], start + 1);
        } else {
            for (const auto& child : p->child) {
                if (match(word, child, start + 1))
                    return true;
            }
        }
        return false;
    }
private:
    TrieNode* root;
};

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * bool param_2 = obj.search(word);
 */

复杂度分析

• 时间复杂度：添加单词为 $O(字符串长度)$，查询为 $O(26 ^ {字符串长度})$。
• 空间复杂度： $O(所有添加了单词的字符串长度 * 26)$。

刷题心得

• 前缀树是挺有意思的应用。
• 不过面试和力扣题目都考察不多，建议大家理解掌握，不必深究。

类似题目：

• ​208. 实现 Trie (前缀树)

参考资料：

• Trie树（Prefix Tree）介绍
• 力扣官方题解

---

OK，以上就是今天题解的全部内容了。如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。
​

我是 @负雪明烛 ，刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。
​

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。
​

• 在刷题的时候，如果你不知道该怎么刷题，可以看 LeetCode 应该怎么刷？
• 如果你觉得题目太多，想在短时间内快速提高，可以看 LeetCode 最经典的 100 道题。

​

祝大家 AC 多多，Offer 多多！我们明天再见！

统计信息

通过次数	提交次数	AC比率
50695	99163	51.1%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
实现 Trie (前缀树)	中等
前缀和后缀搜索	困难