LeetCode Q208: Implement Trie (Prefix Tree)

Implement a trie with insert, search, and startsWith methods.

Note:
You may assume that all inputs are consist of lowercase letters a-z.

	class TrieNode {
	public:
	// Initialize your data structure here.
	TrieNode() {
	wordsEndHere=false;
	memset(subTries, NULL, sizeof(subTries));
	}
	TrieNode(char _c): c(_c){
	wordsEndHere=false;
	memset(subTries, NULL, sizeof(subTries));
	}
	char c;
	bool wordsEndHere;
	TrieNode* subTries[26];
	};
	class Trie {
	public:
	Trie() {
	root = new TrieNode();
	}
	// Inserts a word into the trie.
	void insert(string word) {
	TrieNode* p = root;
	for(int i=0; i<word.length(); i++){
	char c=word[i]-'a';
	if(p->subTries[c]==NULL){
	TrieNode* node=new TrieNode(c);
	p->subTries[c]=node;
	}
	p=p->subTries[c];
	}
	p->wordsEndHere=true;
	}
	// Returns if the word is in the trie.
	bool search(string word) {
	bool found=false;
	TrieNode* p = root;
	for(int i=0; i<word.length(); i++){
	char c=word[i]-'a';
	if(p->subTries[c]==NULL)
	return false;
	p=p->subTries[c];
	}
	return p->wordsEndHere;
	}
	// Returns if there is any word in the trie
	// that starts with the given prefix.
	bool startsWith(string prefix) {
	bool found=false;
	TrieNode* p = root;
	for(int i=0; i<prefix.length(); i++){
	char c=prefix[i]-'a';
	if(i+1==prefix.length()&&p->subTries[c]!=NULL)
	return true;
	if(p->subTries[c]==NULL)
	return false;
	p=p->subTries[c];
	}
	}
	private:
	TrieNode* root;
	};
	// Your Trie object will be instantiated and called as such:
	// Trie trie;
	// trie.insert("somestring");
	// trie.search("key");

view raw Q208ImplementTrie.cpp hosted with ❤ by GitHub