LeetCode 208. Implement Trie (Prefix Tree)

字典树。

测试中有：aaaaaaaaaaa... 的输入，如果每个节点用定长数组存储孩子的话，那就是26^len的空间复杂度（len为输入的长度），内存会不够的。

所以用map<char, TrieNode*>保存其孩子。

代码：

#include <string>
#include <vector>
#include <map>

using namespace std;

class TrieNode
{
public:
	// Initialize your data structure here.
	TrieNode()
	{
		is_word = false;
	}

	void insert(const string& word)
	{
		if (!word.empty())
		{
			nodes[word.front()] =
				nodes[word.front()] != nullptr ?
					nodes[word.front()] : new TrieNode();
			nodes[word.front()]->insert(word.substr(1));
		} else
		{
			is_word = true;
		}
	}

	bool search(string word)
	{
		if (!word.empty())
		{
			if (nodes[word.front()] == nullptr)
			{
				return false;
			} else
			{
				return nodes[word.front()]->search(word.substr(1));
			}
		}
		return is_word;
	}

	bool startsWith(string prefix)
	{
		if (!prefix.empty())
		{
			if (nodes[prefix.front()] == nullptr)
			{
				return false;
			} else
			{
				return nodes[prefix.front()]->startsWith(prefix.substr(1));
			}
		}
		return true;
	}

	// MLE!!!
	// TrieNode* nodes[26];
	map<char, TrieNode*> nodes;
	bool is_word;
};

class Trie
{
public:
	Trie()
	{
		root = new TrieNode();
	}

	// Inserts a word into the trie.
	void insert(string word)
	{
		root->insert(word);
	}

	// Returns if the word is in the trie.
	bool search(string word)
	{
		return root->search(word);
	}

	// Returns if there is any word in the trie
	// that starts with the given prefix.
	bool startsWith(string prefix)
	{
		return root->startsWith(prefix);
	}

private:
	TrieNode* root;
};

LeetCode 208. Implement Trie (Prefix Tree)

原文：http://blog.csdn.net/stephen_wong/article/details/47089819