【Leetcode】211. 添加与搜索单词 - 数据结构设计

一、题目

1、题目描述

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

实现词典类 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 由 '.' 或小写英文字母组成
• 最多调用 10⁴ 次 addWord 和 search

2、基础框架

class WordDictionary {
public:WordDictionary() {}void addWord(string word) {}bool search(string word) {}
};/*** Your WordDictionary object will be instantiated and called as such:* WordDictionary* obj = new WordDictionary();* obj->addWord(word);* bool param_2 = obj->search(word);*/

3、原题链接

211. 添加与搜索单词 - 数据结构设计

二、解题报告

1、思路分析

主要思路同【Leetcode】208.实现Trie（前缀树），但是需要注意，插入的时候只有小写字母字符，而查找的时候有"."和小写字母字符，所以遇到 “.” 字符时，所有子孩子非空的情况都要进行尝试。

2、时间复杂度

3、代码详解

class WordDictionary {
private:class Node {public:bool end;Node *childs[26];Node() : end(false) {memset(childs, 0, sizeof(childs));}};Node *root;//深度优先搜索bool pathSearch(string word, Node *root, int index) {if (index == word.size()) {return root->end;}Node *node = root;int path = 0;if (word[index] == '.') { //字符.for (int i = 0; i < 26; i++) { //所有非空的孩子都要尝试if (node->childs[i]) {bool res = pathSearch(word, node->childs[i], index + 1);if (res) return true;}}return false;} else { //字母字符path = word[index] - 'a';if (node->childs[path] == nullptr) {return false;}return pathSearch(word, node->childs[path], index + 1);}}
public:WordDictionary() {root = new Node();}void addWord(string word) {Node *node = root;int path = 0;for (int i = 0; word[i]; i++) {path = word[i] - 'a';if (node->childs[path] == nullptr) {node->childs[path] = new Node();}node = node->childs[path];}node->end = true;}bool search(string word) {return pathSearch(word, root, 0);}
};/*** Your WordDictionary object will be instantiated and called as such:* WordDictionary* obj = new WordDictionary();* obj->addWord(word);* bool param_2 = obj->search(word);*/