本文共 4328 字，大约阅读时间需要 14 分钟。

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

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

实现词典类 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

来源：力扣（LeetCode）

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

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码

class WordDictionary {
       class TrieNode {
       public:        bool isEnd;        unordered_map
   
     next;        TrieNode() {
               isEnd = false;            next.clear();        }    };public:    TrieNode * root;    /** Initialize your data structure here. */    WordDictionary() {
           root = new TrieNode();    }        /** Adds a word into the data structure. */    void addWord(string word) {
           TrieNode* cur = root;        for (char c: word) {
               if (cur->next.count(c) == 0) {
                   cur->next[c] = new TrieNode();            }            cur = cur->next[c];        }        cur->isEnd = 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 find(word, 0, word.length(), root);    }    bool find(string& word, int start, int end, TrieNode* cur) {
           if (start == end) {
               return cur->isEnd;        }            if (word[start] != '.') {
               if (cur->next.count(word[start]) == 0) {
                   return false;            }            return find(word, start+1, end, cur->next[word[start]]);        } else {
               for (auto iter: cur->next) {
                   bool flag = find(word, start+1, end, cur->next[iter.first]);                if (flag) {
                       return true;                }            }            return false;        }        return false;    }};/** * Your WordDictionary object will be instantiated and called as such: * WordDictionary* obj = new WordDictionary(); * obj->addWord(word); * bool param_2 = obj->search(word); */
   

代码2

前缀树的定义合并到类中。

class WordDictionary {
       bool isEnd;    unordered_map
   
     next;public:    /** Initialize your data structure here. */    WordDictionary() {
           isEnd = false;    }        /** Adds a word into the data structure. */    void addWord(string word) {
           WordDictionary* cur = this;        for (char c: word) {
               if (cur->next.count(c) == 0) {
                   cur->next[c] = new WordDictionary();            }            cur = cur->next[c];        }        cur->isEnd = 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 find(word, 0, word.length(), this);    }    bool find(string& word, int start, int end, WordDictionary* cur) {
           if (start == end) {
               return cur->isEnd;        }            if (word[start] != '.') {
               if (cur->next.count(word[start]) == 0) {
                   return false;            }            return find(word, start+1, end, cur->next[word[start]]);        } else {
               for (auto iter: cur->next) {
                   bool flag = find(word, start+1, end, cur->next[iter.first]);                if (flag) {
                       return true;                }            }            return false;        }        return false;    }};/** * Your WordDictionary object will be instantiated and called as such: * WordDictionary* obj = new WordDictionary(); * obj->addWord(word); * bool param_2 = obj->search(word); */