86ms easy to understand trie solution C++


  • 0
    M
    class Node
    {
    private:
    	char m_content;
    	bool marker;
    	Node *children[26] = { 0, };
    	int children_index = 0;
    	int frequency = 0;
    	int size = 0;
    public:
    	Node() { m_content = ' ', marker = false; }
    	char content() { return m_content; }
    	void set_content(char c) { m_content = c; }
    	bool get_marker() { return marker; }
    	void set_marker() { marker = true; }
    	Node* find_child(char c) { return children[c - 'a']; }
    	void append_child(char c, Node* child) { children[c - 'a'] = child; }
    	Node** get_children() { return children; }
    	void set_frequency() { frequency++; }
    	int get_frequency() { return frequency; }
    	void set_size(int _size) { size = _size; }
    	int get_size() { return size; }
    };
    
    
    
    class WordDictionary {
    private:
    	Node *root;
    public:
        /** Initialize your data structure here. */
        WordDictionary() {root = new Node;}
        
        /** Adds a word into the data structure. */
        void addWord(string word) {
            Node* current = root;
    		if (word.length() == 0)
    		{
    			current->set_marker();
    			return;
    		}
    
    		for (int i = 0; i < word.length(); i++)
    		{
    			Node* child = current->find_child(word[i]);
    			if (child != NULL)
    			{
    				current = child;
    				current->set_frequency();
    			}
    			else
    			{
    				Node* tmp = new Node;
    				tmp->set_content(word[i]);
    				tmp->set_size(current->get_size()+1);
    				current->append_child(word[i], tmp);
    				current = tmp;
    				current->set_frequency();
    			}
    			if (i == word.size() - 1)
    				current->set_marker();
    		}
        }
        
        /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
       void search(string word,bool& is_found) {
    		if (is_found)
    			return;
    		Node* current = root;
    		while (current)
    		{
    			for (int i = 0; i < word.length(); i++)
    			{
    				if (word[i] != '.')
    				{
    					Node* tmp = current->find_child(word[i]);
    					if (!tmp)
    						return;
    					current = tmp;
    				}
    				else
    				{
    					for (int k = 0; k < 26; k++)
    					{
    						char letter = 'a' + k;
    						word[i] = letter;
    						Node* tmp = current->find_child(letter);
    						if(tmp)
    							search(word, is_found);
    					}
    				}
    			}
    			if (current->get_marker()&&current->get_size() == word.size())
    			{
    				is_found = true;
    				return;
    			}
    			else
    				return;
    		}
    		return;
    	}
    	bool search(string word)
    	{
    		bool is_found = false;
    		search(word, is_found);
    		return is_found;
    	}
    };
    

Log in to reply
 

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