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种递归路径。想清楚这个逻辑之后,代码就很好写了。

完整代码如下:

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);
	}
};

本代码提交AC,用时105MS。

Leave a Reply

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