Coding-Problems/LeetCode/Solutions/LC0208.cpp at master · Natansh2005/Coding-Problems · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/*
Problem Statement: https://leetcode.com/problems/implement-trie-prefix-tree/
*/

class TrieNode {
public:
	int words;
	unordered_map<char, TrieNode*> children;
	TrieNode() : words(0) {}
};

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

	void insert(string word) {
		TrieNode* node = root;
		for (char& c: word) {
			if (!node->children.count(c))
				node->children[c] = new TrieNode();
			node = node->children[c];
		}
		node->words++;
	}

	bool search(string word) {
		TrieNode* node = root;
		for (char& c: word) {
			if (!node->children.count(c))
				return false;
			node = node->children[c];
		}
		return node->words;
	}

	bool startsWith(string prefix) {
		TrieNode* node = root;
		for(char& c: prefix) {
			if (!node->children.count(c))
				return false;
			node = node->children[c];
		}
		return true;
	}
};