Leetcode 208实现Trie树前缀

Leetcode 208实现Trie树前缀

一开始使用顺序遍历键值，运行时间太慢，后来修改为使用内置函数lower_bound， upper_bound 查找，速度提升很快；

// 查找前一个键的键值（即小于 k 的最大键）
auto lower = trieMap.lower_bound(k);
// 查找后一个键的键值（即大于 k 的最大键）
auto upper = trieMap.upper_bound(k);

注: 这里的查找均是采用二分查找方式

class Trie {
public:
	// 成员变量
	std::map<string, int> trieMap;
	

	Trie() {

	}

	void insert(string word) {
		trieMap[word] = 1;
	}

	bool search(string word) {
		return trieMap.count(word) == 1;
	}

	bool startsWith(string prefix) 
	{
		if (search(prefix))
			return true;
		string front;
		string back;
		// map内部就是二分查找，速度提高很大
		auto lower = trieMap.lower_bound(prefix);
		if (lower != trieMap.begin())
		{
			--lower;
			front = lower->first;
		}
		else {

		}
		auto upper = trieMap.upper_bound(prefix);
		if (upper != trieMap.end())
		{
			back = upper -> first;
		}
		else {

		}
		if (!front.empty() && front.find(prefix) == 0)
			return true;
		if (!back.empty() && back.find(prefix) == 0)
			return true;
		return false;
	}
};