A C# BFS & DFS Solution by using TrieNode Array


  • 0
    L

    You may switch DFS, BFS solution in method Search.

    public class TrieNode{
        public TrieNode[] Next { get; set; }
        public bool EOW { get; set; }
        public TrieNode() { Next = new TrieNode[26]; EOW = false; }
    }
    public class WordDictionary{
        private TrieNode root;
        public WordDictionary() { root = new TrieNode(); }
        public void AddWord(String word){
            TrieNode cur = root;
            int i = 0;
            while (i < word.Length && cur.Next[word[i] - 'a'] != null)
                cur = cur.Next[word[i++] - 'a'];
            for (; i < word.Length; i++)
                cur = (cur.Next[word[i] - 'a'] = new TrieNode());
            cur.EOW = true;
        }
        public bool Search(string word){
            return WildCard_DFS(word) & WildCard_BFS(word);
            //return WildCard_DFS(word);
            //return WildCard_BFS(word);
        }
        private bool WildCard_BFS(string word){
            TrieNode cur = root;
            Queue<TrieNode> queue = new Queue<TrieNode>();
            queue.Enqueue(cur);
            for (int i = 0; i < word.Length && queue.Count != 0; i++)
            {
                int count = queue.Count;
                while (count-- > 0){
                    cur = queue.Dequeue();
                    if (word[i] == '.'){
                        foreach (var tn in cur.Next)
                            if (tn != null) queue.Enqueue(tn);
                    }
                    else if (cur.Next[word[i] - 'a'] != null)
                        queue.Enqueue(cur.Next[word[i] - 'a']);
                }
            }
            while (queue.Count != 0) //Check EOW
                if (queue.Dequeue().EOW) return true;
            return false;
        }
        private bool WildCard_DFS(string word) { return dfsWildCard(word, root); }
        private bool dfsWildCard(string word, TrieNode root){
            if (word.Length == 1){
                if (word[0] == '.')
                {
                    foreach (var tn in root.Next)
                        if (tn != null && tn.EOW)
                            return true;
                }
                else if (root.Next[word[0] - 'a'] != null && root.Next[word[0] - 'a'].EOW)
                    return true;
                return false;
            }
            if (word[0] == '.'){
                foreach (var tn in root.Next)
                    if (tn != null && dfsWildCard(word.Substring(1), tn))
                        return true;
            }
            else if (root.Next[word[0] - 'a'] != null)
                if (dfsWildCard(word.Substring(1), root.Next[word[0] - 'a']))
                    return true;
            return false;
        }
    }

Log in to reply
 

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