simple c# trie solution


  • 0
    N
    public class WordDictionary {
        public TrieNode Root;
        /** Initialize your data structure here. */
        public WordDictionary() {
            this.Root = new TrieNode();
        }
        
        /** Adds a word into the data structure. */
        public void AddWord(string word) {
            var node = this.Root;
            foreach(var c in word){
                if(c=='.'){
                    node.Children[26] = new TrieNode();
                    node = node.Children[26];
                }
                else{
                    if(node.Children[c-'a'] == null){
                        node.Children[c-'a'] = new TrieNode();
                    }
                    node = node.Children[c-'a'];
                }
            }
            
            node.IsEnd = true;
        }
        
        /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
        public bool Search(string word) {
            return Search(word, this.Root);
        }
        
        public bool Search(string word, TrieNode node){
            for(var i=0;i<word.Length;i++){
                var c = word[i];
                if(c!='.'){
                    if(node.Children[c-'a'] == null) return false;
                    node = node.Children[c-'a'];
                }
                else{
                    if(i==word.Length-1) {
                        foreach(var child in node.Children){
                            if(child!=null && child.IsEnd) return true;
                        }
                        return false;
                    }                var sub = word.Substring(i+1);
                    foreach(var child in node.Children){
                        if(child==null) continue;
                        if(Search(sub, child)) return true;
                    }
                    return false;
                }
            }
            
            return node.IsEnd;
        }
        
        public class TrieNode{
            public TrieNode[] Children;
            public bool IsEnd;
            public TrieNode(){
                this.Children = new TrieNode[27];
            }
        }
    }
    

Log in to reply
 

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