[LeetCode]Implement Magic Dictionary

Trie的题目，和这道题几乎是一样的。如果需要一个flag来表示我们当前有没有modify word，没有的话我们按照match dot 的方式来搜索，否则，我们严格match当前的字符，因为只允许我们modify一次。最后check的时候也要走注意string一定要modify过才可以return true。代码如下：

	class MagicDictionary {
	public:
	/** Initialize your data structure here. */
	MagicDictionary() {
	m_root = new Node();
	}
	/** Build a dictionary through a list of words */
	void buildDict(vector<string> dict) {
	for(auto& s : dict)
	m_root = insert(s, 0, m_root);
	}
	/** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */
	bool search(string word) {
	return search(word, 0, m_root, false);
	}
	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, bool modified)
	{
	if(!curr)
	return false;
	if(idx == word.size())
	return curr->isWord && modified;
	char c = word[idx];
	if(!modified)
	{
	for(auto& p : curr->children)
	{
	if(search(word, idx + 1, p.second, p.first != c))
	return true;
	}
	return false;
	}
	else
	return search(word, idx + 1, (curr->children)[c], modified);
	}
	};
	/**
	* Your MagicDictionary object will be instantiated and called as such:
	* MagicDictionary obj = new MagicDictionary();
	* obj.buildDict(dict);
	* bool param_2 = obj.search(word);
	*/

view raw Implement Magic Dictionary.cpp hosted with ❤ by GitHub