LeetCode Add and Search Word – Data structure design

LeetCode 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.

实现一个字典,要求可以插入单词和搜索单词,并且支持一种正则表达式,即点号’.’表示任意一个字符。 本题明显是用Trie树来做,插入和搜索普通字符串的方法和Trie树是一模一样的。 唯一需要注意的是搜索带点号的字符串,此时用递归来做,递归的出口是,当遍历到字符串的最后一个字符时,根据是否为点号进行判断。递归向下的过程也是分是否为点号的,如果是点号,则需要尝试26种递归路径。想清楚这个逻辑之后,代码就很好写了。 完整代码如下: [cpp] const int N = 26; class WordDictionary { private: struct Node { bool isWord; vector<Node*> children; Node(bool i) :isWord(i) { for (int i = 0; i < N; ++i)children.push_back(NULL); }; }; Node *root; bool search(const string& word, int i, Node *root) { if (root == NULL)return false; int idx = word[i] – ‘a’; if (i == word.size() – 1) { if (word[i] != ‘.’)return root->children[idx] != NULL&&root->children[idx]->isWord; else { for (int j = 0; j < N; ++j) { if (root->children[j] != NULL&&root->children[j]->isWord)return true; } return false; } } if (word[i] != ‘.’)return search(word, i + 1, root->children[idx]); else { for (int j = 0; j < N; ++j) { if (search(word, i + 1, root->children[j]))return true; } return false; } } public: /** Initialize your data structure here. */ WordDictionary() { root = new Node(false); } /** Adds a word into the data structure. */ void addWord(string word) { Node *cur = root; for (const auto& c : word) { int idx = c – ‘a’; if (cur->children[idx] == NULL)cur->children[idx] = new Node(false); cur = cur->children[idx]; } cur->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) { Node *cur = root; return search(word, 0, cur); } }; [/cpp] 本代码提交AC,用时105MS。]]>

Leave a Reply

Your email address will not be published. Required fields are marked *