Dynamic allocation Trie implementation 50 ms, 98%


  • 0
    I

    Code is long, readability is traded for speed... I personally do not recommend solving this question in such a nasty way. (I don't think I can do it in 30 mins)

    class TrieNode {
        public:
        	// Initialize your data structure here.
        	TrieNode* subnode;
        	TrieNode* next;
        		char key;
        	TrieNode() {
        		subnode = nullptr;
        		next = nullptr;
        		key = '^';
        	}
        
        	TrieNode(char input)
        	{
        		subnode = nullptr;
        		next = nullptr;
        		key = input;
        	}
        };
        
        class Trie {
        public:
        	Trie() {
        		root = new TrieNode();
        	}
        
        	// Inserts a word into the trie.
        	void insert(string word) {
        		int len = word.size();
        		TrieNode* cur_ptr = root;
        		for (int i = 0; i<len; i++)
        		{
        			TrieNode* node = cur_ptr->subnode;
        			bool flag = false;
        			for (; node != nullptr && node->key < word[i];)
        			{
        				cur_ptr = node;
        				node = node->next;
        				flag = true;
        			}
        
        			if (node != nullptr)
        			{
        				if (node->key > word[i])
        				{
        					// insert the key
        					if (flag)
        					{
        						cur_ptr->next = new TrieNode(word[i]);
        						cur_ptr->next->next = node;
        						cur_ptr = cur_ptr->next;
        					}
        					else
        					{
        						cur_ptr->subnode = new TrieNode(word[i]);
        						cur_ptr->subnode->next = node;
        						cur_ptr = cur_ptr->subnode;
        					}
        				}
        				else
        					cur_ptr = node;
        			}
        			else
        			{
        				if (!flag)
        				{
        					cur_ptr->subnode = new TrieNode(word[i]);
        					cur_ptr = cur_ptr->subnode;
        				}
        				else
        				{
        					cur_ptr->next = new TrieNode(word[i]);
        					cur_ptr = cur_ptr->next;
        				}
        			}
        
        		}
        
        
        		if (cur_ptr->subnode == nullptr)
        		{
        			cur_ptr->subnode = new TrieNode('\0');
        		}
        		else
        		{
        			if (cur_ptr->subnode->key != '\0')
        			{
        				TrieNode *tmp = cur_ptr->subnode;
        				cur_ptr->subnode = new TrieNode('\0');
        				cur_ptr->subnode->next = tmp;
        			}
        		}
        		
        		return;
        
        	}
        
        	// Returns if the word is in the trie.
        	bool search(string word) {
        		int len = word.size();
        		TrieNode* cur_ptr = root;
        		for (int i = 0; i<len; i++)
        		{
        			char cur = word[i];
        			TrieNode* node = cur_ptr->subnode;
        			for (;node!=nullptr && node->key<word[i];)
        				node = node->next;
        			if (node == nullptr || node->key > word[i])
        				return false;
        			else
        				cur_ptr = node;
        		}
        
        		for (cur_ptr=cur_ptr->subnode;cur_ptr!=nullptr;)
        		{
        			if (cur_ptr->key == '\0')
        				return true;
        			else
        				cur_ptr = cur_ptr->next;
        		}
        		return false;
        
        	}
        
        	// Returns if there is any word in the trie
        	// that starts with the given prefix.
        	bool startsWith(string prefix) {
        		int len = prefix.size();
        		TrieNode* cur_ptr = root;
        		for (int i = 0; i<len; i++)
        		{
        			char cur = prefix[i];
        			TrieNode* node = cur_ptr->subnode;
        			for (; node != nullptr && node->key<prefix[i];)
        				node = node->next;
        			if (node == nullptr || node->key > prefix[i])
        				return false;
        			else
        				cur_ptr = node;
        		}
        		return true;
        	}
        
        private:
        	TrieNode* root;
        };

Log in to reply
 

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