C# - TrieNode solution - clean code


  • 1

    If you combine the logic for the 3 methods using a helper you can really reduce the code quite a bit.

    public class Trie {
    
        TrieNode root;
        
        /** Initialize your data structure here. */
        public Trie() 
        {
            root = new TrieNode();
        }
        
        /** Inserts a word into the trie. */
        public void Insert(string word) 
        {
            GetEndNode(word, true);
        }
        
        /** Returns if the word is in the trie. */
        public bool Search(string word) 
        {
            TrieNode node = GetEndNode(word, false);
            return node != null && node.isWord;
        }
        
        /** Returns if there is any word in the trie that starts with the given prefix. */
        public bool StartsWith(string prefix) 
        {
            TrieNode node = GetEndNode(prefix, false);
            return node != null;  
        }
        
        public TrieNode GetEndNode(string word, bool insert)
        {
            TrieNode node = root;
            int wordIndex = 0;
            while (node != null && wordIndex < word.Length)
            {
                int nodeIndex = word[wordIndex] - 'a';
                if (insert && node.nodes[nodeIndex] == null) node.nodes[nodeIndex] = new TrieNode();
                node = node.nodes[nodeIndex];
                wordIndex++;
            }
            
            if (insert) node.isWord = true;
            return node;
        }
    }
    
    public class TrieNode
    {
        public bool isWord;
        public TrieNode[] nodes = new TrieNode[26];
    }
    
    

Log in to reply
 

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