[LeetCode]Add and Search Word - Data structure design

实现Trie的题目，具体可以参考这篇文章。这道题需要注意的就是处理“.”，其可以match任意字符，所以碰到period的时候我们就要考虑所有的子节点，如果任何一个子节点返回true，那么当前节点也return true。代码如下：

	class WordDictionary {
	public:
	/** Initialize your data structure here. */
	WordDictionary() {
	m_root = new Node();
	}
	/** Adds a word into the data structure. */
	void addWord(string word) {
	m_root = insert(word, 0, m_root);
	}
	/** 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 search(word, 0, m_root);
	}
	private:
	struct Node
	{
	bool isWord;
	unordered_map<char, Node*> children;
	};
	Node* m_root;
	Node* insert(string word, int idx, Node* curr)
	{
	if(!curr)
	curr = new Node();
	if(idx == word.size())
	{
	curr->isWord = true;
	return curr;
	}
	char c = word[idx];
	Node* next = insert(word, idx + 1, (curr->children)[c]);
	(curr->children)[c] = next;
	return curr;
	}
	bool search(string word, int idx, Node* curr)
	{
	if(!curr)
	return false;
	if(idx == word.size())
	return curr->isWord;
	char c = word[idx];
	if(c == '.')
	{
	for(auto& p : curr->children)
	{
	if(search(word, idx + 1, p.second))
	return true;
	}
	return false;
	}
	else
	return search(word, idx + 1, (curr->children)[c]);
	}
	};

view raw Add and Search Word - Data structure design.cpp hosted with ❤ by GitHub