C# Trie


  • 0
    H
    public class TrieNode {
            public Dictionary<char, TrieNode> nodes = new Dictionary<char, TrieNode>();
            public bool isWord = false;
        }
    
        public TrieNode root = new TrieNode();
        // Adds a word into the data structure.
        public void AddWord(String word) {
            TrieNode cur = root;
            foreach(char c in word) {
                if (!cur.nodes.ContainsKey(c)) cur.nodes[c] = new TrieNode();
                cur = cur.nodes[c];
            }
            
            cur.isWord = 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, TrieNode cur = null, int p = 0) {
            if (cur == null) cur = root;
            if (p >= word.Length) return cur.isWord;
            
            if (word[p] == '.') {
                for(int i = 0; i < 26; i++) {
                    char c = (char)('a' + i);
                    if (!cur.nodes.ContainsKey(c)) continue;
                    if (Search(word, cur.nodes[c], p + 1)) return true;
                }
            } else {
                char c = word[p];
                if (cur.nodes.ContainsKey(c) && Search(word, cur.nodes[c], p + 1)) return true;
            }
            
            return false;
        }
    

Log in to reply
 

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