C++实现LeetCode(211.添加和查找单词-数据结构设计)_C/C++

C++实现LeetCode(211.添加和查找单词-数据结构设计)

2021-12-14 14:54Grandyang C/C++

这篇文章主要介绍了C++实现LeetCode(211.添加和查找单词-数据结构设计),本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下

[LeetCode] 211.Add and Search Word - Data structure design 添加和查找单词-数据结构设计

Design a data structure that supports the following two operations:

void addWord(word)
bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

For example:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

Note:
You may assume that all words are consist of lowercase letters a-z.

click to show hint.

You should be familiar with how a Trie works. If not, please work on this problem: Implement Trie (Prefix Tree) first.

LeetCode出新题的速度越来越快了，有点跟不上节奏的感觉了。这道题如果做过之前的那道 Implement Trie (Prefix Tree) 实现字典树(前缀树)的话就没有太大的难度了，还是要用到字典树的结构，唯一不同的地方就是search的函数需要重新写一下，因为这道题里面'.'可以代替任意字符，所以一旦有了'.'，就需要查找所有的子树，只要有一个返回true，整个search函数就返回true，典型的DFS的问题，其他部分跟上一道实现字典树没有太大区别，代码如下：

				?

									class WordDictionary {

									public:

									    struct TrieNode {

									    public:

									        TrieNode *child[26];

									        bool isWord;

									        TrieNode() : isWord(false) {

									            for (auto &a : child) a = NULL;

									        }

									    };

									    WordDictionary() {

									        root = new TrieNode();

									    }

									    // Adds a word into the data structure.

									    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;

									    }

									    // 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 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;

									};

									// Your WordDictionary object will be instantiated and called as such:

									// WordDictionary wordDictionary;

									// wordDictionary.addWord("word");

									// wordDictionary.search("pattern");