Medium

题目描述

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

实现 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"); // 返回 False
wordDictionary.search("bad"); // 返回 True
wordDictionary.search(".ad"); // 返回 True
wordDictionary.search("b.."); // 返回 True

提示：

  • 1 <= word.length <= 25
  • addWord 中的 word 由小写英文字母组成
  • search 中的 word 由 '.' 或小写英文字母组成
  • 最多会有 2 个 '.' 在 search 查询中
  • 最多 10^4 次 addWord 和 search 调用

解题思路

这道题是字典树（Trie）的经典应用，需要支持通配符 . 的搜索功能。

核心思路：

  1. 数据结构选择：使用字典树（Trie）存储所有添加的单词，每个节点包含26个子节点（对应a-z）和一个布尔标记表示是否为单词结尾。

  2. addWord操作：从根节点开始，按字符逐层向下构建路径，在单词末尾节点标记为单词结尾。

  3. search操作：这是关键部分，需要处理通配符 .：

    • 如果当前字符是普通字母，直接沿对应路径向下
    • 如果遇到 .，需要尝试所有可能的子节点（深度优先搜索）
    • 到达字符串末尾时，检查当前节点是否标记为单词结尾

算法步骤：

  • 构建字典树节点结构，包含children数组和isEnd标记
  • addWord：逐字符插入，最后标记结尾
  • search：使用DFS递归处理，遇到 . 时遍历所有子节点

推荐解法：字典树 + DFS，时间复杂度最优，代码简洁清晰。

代码实现

class WordDictionary {
private:
    struct TrieNode {
        TrieNode* children[26];
        bool isEnd;
        
        TrieNode() {
            for (int i = 0; i < 26; i++) {
                children[i] = nullptr;
            }
            isEnd = false;
        }
    };
    
    TrieNode* root;
    
    bool dfs(string& word, int index, TrieNode* node) {
        if (index == word.length()) {
            return node->isEnd;
        }
        
        char c = word[index];
        if (c == '.') {
            for (int i = 0; i < 26; i++) {
                if (node->children[i] && dfs(word, index + 1, node->children[i])) {
                    return true;
                }
            }
            return false;
        } else {
            int idx = c - 'a';
            return node->children[idx] && dfs(word, index + 1, node->children[idx]);
        }
    }
    
public:
    WordDictionary() {
        root = new TrieNode();
    }
    
    void addWord(string word) {
        TrieNode* node = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!node->children[idx]) {
                node->children[idx] = new TrieNode();
            }
            node = node->children[idx];
        }
        node->isEnd = true;
    }
    
    bool search(string word) {
        return dfs(word, 0, root);
    }
};

class WordDictionary:
    def __init__(self):
        self.root = {}
    
    def addWord(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node:
                node[char] = {}
            node = node[char]
        node['#'] = True  # 标记单词结尾
    
    def search(self, word: str) -> bool:
        def dfs(word, index, node):
            if index == len(word):
                return '#' in node
            
            char = word[index]
            if char == '.':
                for key in node:
                    if key != '#' and dfs(word, index + 1, node[key]):
                        return True
                return False
            else:
                if char in node:
                    return dfs(word, index + 1, node[char])
                return False
        
        return dfs(word, 0, self.root)

public class WordDictionary {
    private class TrieNode {
        public TrieNode[] Children;
        public bool IsEnd;
        
        public TrieNode() {
            Children = new TrieNode[26];
            IsEnd = false;
        }
    }
    
    private TrieNode root;
    
    public WordDictionary() {
        root = new TrieNode();
    }
    
    public void AddWord(string word) {
        TrieNode node = root;
        foreach (char c in word) {
            int index = c - 'a';
            if (node.Children[index] == null) {
                node.Children[index] = new TrieNode();
            }
            node = node.Children[index];
        }
        node.IsEnd = true;
    }
    
    public bool Search(string word) {
        return DFS(word, 0, root);
    }
    
    private bool DFS(string word, int index, TrieNode node) {
        if (index == word.Length) {
            return node.IsEnd;
        }
        
        char c = word[index];
        if (c == '.') {
            for (int i = 0; i < 26; i++) {
                if (node.Children[i] != null && DFS(word, index + 1, node.Children[i])) {
                    return true;
                }
            }
            return false;
        } else {
            int idx = c - 'a';
            return node.Children[idx] != null && DFS(word, index + 1, node.Children[idx]);
        }
    }
}

var WordDictionary = function() {
    this.root = {};
};

WordDictionary.prototype.addWord = function(word) {
    let node = this.root;
    for (let char of word) {
        if (!node[char]) {
            node[char] = {};
        }
        node = node[char];
    }
    node.isEnd = true;
};

WordDictionary.prototype.search = function(word) {
    const dfs = (node, index) => {
        if (index === word.length) {
            return !!node.isEnd;
        }
        
        const char = word[index];
        if (char === '.') {
            for (let key in node) {
                if (key !== 'isEnd' && dfs(node[key], index + 1)) {
                    return true;
                }
            }
            return false;
        } else {
            return node[char] && dfs(node[char], index + 1);
        }
    };
    
    return dfs(this.root, 0);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
addWordO(m)O(m)
searchO(n × 26^k)O(h)

其中：

  • m 是添加单词的长度
  • n 是搜索单词的长度
  • k 是搜索单词中 ‘.’ 的个数
  • h 是字典树的高度（递归栈深度）
  • 总空间复杂度：O(ALPHABET_SIZE × N × M)，N是单词数量，M是平均长度

相关题目