C++/C# simple solution


  • 4
    O

    C++ version

    class TrieNode {
    public:
        bool HasValue;
        TrieNode** Children;
        // Initialize your data structure here.
        TrieNode() {
            Children = new TrieNode*[26]();
            HasValue = false;
        }
        
        ~TrieNode(){
            for (int i = 0; i < 26; i++)
            {
                delete Children[i]; // delete NULL is safe, a no-op.
            }
            delete[] Children;
        }    
    };
    
    class Trie {
    public:
        Trie() {
            root = new TrieNode();
        }
    
        // Inserts a word into the trie.
        void insert(string word) {
            getNode(word, true)->HasValue = true;         
        }
    
        // Returns if the word is in the trie.
        bool search(string word) {
           TrieNode* pNode = getNode(word, false);
            return (pNode != NULL && pNode->HasValue);  
        }
    
        // Returns if there is any word in the trie
        // that starts with the given prefix.
        bool startsWith(string prefix) {
            return (getNode(prefix, false) != NULL); 
        }
    
    private:
        TrieNode* root;
        TrieNode* getNode(string word, bool create){
            TrieNode* pNode = root;
            int id;
            int n = word.size();
            for (int i = 0; i <n; ++i)
            {
              id = word[i] - 'a';
              if (pNode->Children[id] == NULL){
                  if(create)
                    pNode->Children[id] = new TrieNode();
                  else
                    return NULL;
              }
              pNode = pNode->Children[id];
            }
    
            return pNode;        
        }   
    };
    

    C# version

    class TrieNode {
        public bool HasValue;
        public TrieNode[] Children;
        // Initialize your data structure here.
        public TrieNode() {
            Children = new TrieNode[26];
            HasValue = false;
        }
    }
    
    public class Trie {
        private TrieNode root;
    
        public Trie() {
            root = new TrieNode();
        }
        
        private TrieNode GetNode(string word, bool create)
        {
            TrieNode node = root;
            int id;
            foreach (char cr in word)
            {
              id = cr - 'a';
              if (node.Children[id] == null){
                  if(create)
                    node.Children[id] = new TrieNode();
                  else
                    return null; 
              }
                
              node = node.Children[id];
            }
    
            return node;
        }    
    
        // Inserts a word into the trie.
        public void Insert(String word) {
            GetNode(word, true).HasValue = true;
        }
    
        // Returns if the word is in the trie.
        public bool Search(string word) {
            var node = GetNode(word, false);
            return (node != null && node.HasValue);        
        }
    
        // Returns if there is any word in the trie
        // that starts with the given prefix.
        public bool StartsWith(string word) {
            return GetNode(word, false) != null;        
        }
    }

Log in to reply
 

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