C# beats 88% simple not optimized array for nodes


  • 1
    P
        class TrieNode
        {
            // Initialize your data structure here.
            public TrieNode()
            {
                _chars = new TrieNode['z' - 'a' + 1];
                IsEndOfWord = false;
            }
            
            public TrieNode GetNode(char c)
            {
                return _chars[c - 'a'];
            }
    
            public bool IsEndOfWord {get; set;}
    
            public TrieNode AddNode(char c)
            {
                TrieNode newNode = new TrieNode();
                _chars[c - 'a'] = newNode;
                return newNode;
            }
    
            private TrieNode[] _chars;        
        }
    
        public class Trie
        {
            private TrieNode root;
    
            public Trie()
            {
                root = new TrieNode();
            }
    
            // Inserts a word into the trie.
            public void Insert(String word)
            {
                if (string.IsNullOrEmpty(word))
                    return;
    
                TrieNode node = root;
                foreach(char c in word)
                {
                    TrieNode nextNode = node.GetNode(c);
                    if (nextNode == null)
                    {
                        node = node.AddNode(c);
                    }
                    else 
                    {
                        node = nextNode;
                    }
                }
                node.IsEndOfWord = true;
            }
    
            // Returns if the word is in the trie.
            public bool Search(string word)
            {
                TrieNode lastNode = LastNodeFor(word);
                return lastNode != null && lastNode.IsEndOfWord;
            }
    
            // Returns if there is any word in the trie
            // that starts with the given prefix.
            public bool StartsWith(string word)
            {
                return LastNodeFor(word) != null;
            }
    
            private TrieNode LastNodeFor(string word)
            {
                TrieNode node = root;
                foreach (char c in word)
                {
                    TrieNode nextNode = node.GetNode(c);
                    if (nextNode == null)
                    {
                        return null;
                    }
                    else
                    {
                        node = nextNode;
                    }
                }
                return node;        
            }
        }
    

Log in to reply
 

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