My C++ solution


  • 0
    A
    class TrieNode {
    public:
    	// Initialize your data structure here.
    	TrieNode(char c = 0) {
    		isEnd = false;
    		content = c;
    	}
    	TrieNode *subNode(char c)
    	{
    		if(childList.size() != 0)
    		{
    			for(int i = 0; i < childList.size(); i++)
    			{
    				if(childList[i]->content == c)
    					return childList[i];
    			}
    		}
    		return NULL;
    	}
    public:
    	char content;
    	bool isEnd;
    	vector<TrieNode *> childList;
    };
    
    class Trie {
    public:
    	Trie() {
    		root = new TrieNode();
    	}
    
    	// Inserts a word into the trie.
    	void insert(string s) {
    		if(search(s) == true)
    			return;
    		TrieNode *cur = root;
    		for(int i = 0; i < s.length(); i++)
    		{
    			TrieNode *child = cur->subNode(s[i]);
    			if(child == NULL)
    			{
    				TrieNode * temp = new TrieNode(s[i]);
    				cur->childList.push_back(temp);
    				cur = temp;
    			}
    			else
    				cur = child;
    		}
    		cur->isEnd = true;
    	}
    
    	// Returns if the word is in the trie.
    	bool search(string key) {
    		TrieNode *cur = root;
    		for(int i = 0; i < key.length(); i++)
    		{
    			TrieNode *child = cur->subNode(key[i]);
    			if(child == NULL)
    				return false;
    			cur = child;
    		}
    		return cur->isEnd;
    	}
    
    	// Returns if there is any word in the trie
    	// that starts with the given prefix.
    	bool startsWith(string prefix) {
    
    		TrieNode *cur = root;
    		for(int i = 0; i < prefix.length(); i++)
    		{
    			TrieNode *child = cur->subNode(prefix[i]);
    			if(child == NULL)
    				return false;
    			cur = child;
    		}
    		return true;
    	}
    
    private:
    	TrieNode* root;
    };
    
    // Your Trie object will be instantiated and called as such:
    // Trie trie;
    // trie.insert("somestring");
    // trie.search("key");

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.