test demo

mapsun.hpp

// https://www.lintcode.com/problem/map-sum-pairs/description
class MapSum {

	class TrieNode {
	public:
		unordered_map<char, TrieNode*> children;
		int val = 0;

		TrieNode() {}
		TrieNode(const int& val) : val(val) {
		}
		~TrieNode() {
			for (auto& pair: children) {
				delete pair.second;
			}
		}
	};

	

public:
	TrieNode* root = new TrieNode();
	MapSum() {}
	~MapSum() {
		delete root;
	}

	void insert(const string& key, int val) {
		TrieNode* node = root;
		for (char c : key) {
			auto it = node->children.find(c);
			if (it == node->children.end()) {
				TrieNode* next = new TrieNode();
				node->children.insert(make_pair(c, next));
				node = next;
			}
			else {
				node = it->second;
			}
		}
		node->val = val;
	}

	int sum(const string& prefix) {
		TrieNode* node = root;

		for (char c : prefix) {
			auto it = node->children.find(c);
			if (it == node->children.end()) {
				return 0;
			}
			node = it->second;
		}
		int sum = 0;
		sumChildren(node, sum);
		return sum;
	}

	void sumChildren(TrieNode* node, int& sum) {
		sum += node->val;
		for (auto& pair: node->children) {
			sumChildren(pair.second, sum);
		}
	}
};

void testMapSum() {
	MapSum ms;
	ms.insert("apple", 3);
	cout << ms.sum("ap") << endl;
	ms.insert("apple", 5);
	cout << ms.sum("ap") << endl;
	ms.insert("app", 2);
	cout << ms.sum("ap") << endl;
	ms.insert("appe", 5);
	cout << ms.sum("ap") << endl;
}

#endif // !MAP_SUM_H