Short C# Solution by using Dictionary


  • 0
    L
    class TrieNode{
        public char CH { get; set; }
        public Dictionary<char, TrieNode> Next { get; set; }
        public bool EOW { get; set; }
        public TrieNode(char ch) {
            CH = ch; Next = new Dictionary<char, TrieNode>(); EOW = false;
        }
    }
    public class Trie{
        private TrieNode root;
        public Trie(){ root = new TrieNode('\0'); }
        // Inserts a word into the trie.
        public void Insert(String word) {
            TrieNode cur = root;
            int i = 0;
            while (i < word.Length && cur.Next.ContainsKey(word[i]))
                cur = cur.Next[word[i++]];
            for (; i < word.Length; i++)
                cur = (cur.Next[word[i]] = new TrieNode(word[i]));
            cur.EOW = true;
        }
        // Returns if the word is in the trie.
        public bool Search(string word){
            TrieNode cur = root;
            for (int i = 0; i < word.Length; cur = cur.Next[word[i++]])
                if (!cur.Next.ContainsKey(word[i])) return false;
            return cur.EOW;
        }
        // Returns if there is any word in the trie that starts with the given prefix.
        public bool StartsWith(string word){
            TrieNode cur = root;
            for (int i = 0; i < word.Length; cur = cur.Next[word[i++]])
                if (!cur.Next.ContainsKey(word[i])) return false;
            return true;
        }
    }

Log in to reply
 

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