[LeetCode]Implement Trie (Prefix Tree)

Trie的基本操作的实现，细节可以参考这篇文章。代码如下：

	class Trie {
	public:
	/** Initialize your data structure here. */
	Trie() {
	_root = new node();
	}
	/** Inserts a word into the trie. */
	void insert(string word) {
	_root = insert(word, 0, _root);
	}
	/** Returns if the word is in the trie. */
	bool search(string word) {
	node* curr = _root;
	int i = 0;
	while(curr && i < word.size())
	curr = (curr->children)[word[i++]];
	return curr? curr->isWord: false;
	}
	/** Returns if there is any word in the trie that starts with the given prefix. */
	bool startsWith(string prefix) {
	node* curr = _root;
	int i = 0;
	while(curr && i < prefix.size())
	curr = (curr->children)[prefix[i++]];
	return curr;
	}
	private:
	struct node
	{
	bool isWord;
	unordered_map<char, node*> children;
	};
	node* _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;
	}
	};

view raw Implement Trie (Prefix Tree).cpp hosted with ❤ by GitHub