Beats 90% - using Array of 26 chars


  • 0
    public class Trie //For solving Q208 from Leetcode
    {
        TrieNode root;
    
        /** Initialize your data structure here. */
        public Trie()
        {
            root = new TrieNode();
        }
    
        /** Inserts a word into the trie. */
        public void Insert(string word)
        {
            TrieNode[] children = root.Children;
            for (int i = 0; i < word.Length; i++)
            {
                int ch = word[i] - 'a';
                if(children[ch]!=null) //if we have seen it before
                {
                    if (i == word.Length - 1)
                        children[ch].isLeaf = true;
                }
                //if we have not seen this at this level.
                else
                {
                    children[ch] = new TrieNode(word[i]);
                    if (i == word.Length - 1)//last char
                    {
                        children[ch].isLeaf = true;
                    }
                }
                children = children[ch].Children;
            }
        }
    
        /** Returns if the word is in the trie. */
        public bool Search(string word)
        {
            TrieNode[] children = root.Children;
    
            for (int i = 0; i < word.Length; i++)
            {
                int ch = word[i] - 'a';
                if (children[ch] == null)
                    return false;
                else
                {
                    if (i == word.Length - 1 && children[ch].isLeaf == true)//last character
                        return true;
    
                    children = children[ch].Children;
                }
            }
            return false;
        }
    
        /** Returns if there is any word in the trie that starts with the given prefix. */
        public bool StartsWith(string prefix)
        {
            TrieNode[] children = root.Children;
            for(int i=0; i<prefix.Length; i++)
            {
                int ch = prefix[i]-'a';
                if (children[ch] == null)
                    return false;
                else
                {
                    if (i == prefix.Length - 1)
                        return true;
                }
                children = children[ch].Children;
            }
            return false;
        }
    }
    
    public class TrieNode
    {
        public char c;
        public TrieNode[] Children;
        public bool isLeaf;
        public TrieNode()
        {
            Children = new TrieNode[26];
        }
    
        public TrieNode(char ch)
        {
            c = ch;
            Children = new TrieNode[26];
        }
    }
    

Log in to reply
 

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