LeetCode 208. Implement Trie (Prefix Tree)

题目：https://leetcode.com/problems/implement-trie-prefix-tree/
思路：
前缀树的概念，参考这里。谷歌搜到的，其实有一大把~
判断是否有这么个“儿子”的时候，增加了一个hasEnd布尔值，如果有以这个点为结束的字符则设置成true.
限制：为了实现方便，现在只能存储a-z共26个字符，如果再扩展可以考虑用map来存字符对应的孩子指针。
单词的字符数量为M，插入节点的时间复杂度是O(M)
startWith(..)和search(..)一大半部分可以合并
代码：

class TrieNode {
public:
	bool hasEnd;
	TrieNode** children;
	// Initialize your data structure here.
	TrieNode() {
		children = NULL;
		hasEnd = false;
	}
	bool hasChild(char c) {
		if (NULL == children)
			return false;
		return !(NULL == children[c - 'a']);
	}
	TrieNode* addChild(char c) {
		if (NULL == children) {
			children = new TrieNode*[26];
			for (int i = 0; i<26; i++)
				children[i] = NULL;
		}
		int pos = c - 'a';
		children[pos] = new TrieNode;
		return children[pos];
	}
};
class Trie {
public:
	Trie() {
		root = new TrieNode();
	}
	// Inserts a word into the trie.
	void insert(string word) {
		int wordSz = word.size();
		char c;
		TrieNode *currNode = root;
		for (int i = 0; i<wordSz; i++) {
			c = word[i];
			if (currNode->hasChild(c))
				currNode = currNode->children[c - 'a'];
			else {
				currNode = currNode->addChild(c);
			}
			if (i == wordSz - 1)
				currNode->hasEnd = true;
		}
	}
	// Returns if the word is in the trie.
	bool search(string word) {
		int wordSz = word.size();
		char c;
		TrieNode *currNode = root;
		for (int i = 0; i<wordSz; i++) {
			c = word[i];
			if (currNode->hasChild(c))
				currNode = currNode->children[c - 'a'];
			else
				return false;
		}
		return currNode->hasEnd;
	}
	// Returns if there is any word in the trie
	// that starts with the given prefix.
	bool startsWith(string prefix) {
		int wordSz = prefix.size();
		char c;
		TrieNode *currNode = root;
		for (int i = 0; i<wordSz; i++) {
			c = prefix[i];
			if (currNode->hasChild(c))
				currNode = currNode->children[c - 'a'];
			else
				return false;
		}
		return true;
	}
private:
	TrieNode* root;
};
// Your Trie object will be instantiated and called as such:
// Trie trie;
// trie.insert("somestring");
// trie.search("key");