C# solution: Trie and DFS


  • 0
    B

    Be careful:

    After match a word:

    1. // to avoid find the same word twice
      curTrieNode.IsFinished = false;
    2. // to avoid "bend", "benda", the search does not search for "benda"
      // do not add "return" after add a word into the result list.
    public class Solution {
        public IList<string> FindWords(char[,] board, string[] words) 
        {
            var row = board.GetLength(0);
            var col = board.GetLength(1);
    
            var trie = new Trie();
    
            foreach(var word in words)
            {
                trie.Insert(word);
            }
    
            var isVisited = new bool[row, col];
    
            var result = new List<string>();
    
            for (int i = 0; i < row; i++)
            {
                for (int j = 0; j < col; j++)
                {
                    DFS(board, i, j, isVisited, trie.Root, result);
                }
            }
    
            return result;
        }
    
        private void DFS(char[,] board, int i, int j, bool[,] isVisited, TrieNode trieNode, List<string> result)
        {
            var row = board.GetLength(0);
            var col = board.GetLength(1);
    
            if (i < 0 || i >= row || j < 0 || j >= col) return;
            if (isVisited[i, j]) return;
    
            var trieNodeIndex = board[i,j] - 'a';
            
            var curTrieNode = trieNode.Nodes[trieNodeIndex];
    
            if (curTrieNode == null) return;
            
            //Console.WriteLine("i:" + i + "  j:" + j + "  board:" + board[i,j] + "  " + curTrieNode.Word);
    
            if (curTrieNode.IsFinished)
            {
                // to avoid find the same word twice
                curTrieNode.IsFinished = false;
                result.Add(curTrieNode.Word);
                
                // to avoid "bend", "benda", the search does not search for "benda"
                //return;
            }
    
            var directions = new Tuple<int,int>[]{ Tuple.Create(-1,0), Tuple.Create(1,0), Tuple.Create(0,1), Tuple.Create(0,-1) };
            
            isVisited[i,j] = true;
    
            foreach(var direction in directions)
            {
                var nextI = i + direction.Item1;
                var nextJ = j + direction.Item2;
    
                DFS(board, nextI, nextJ, isVisited, curTrieNode, result);
            }
    
            isVisited[i, j] = false;
        }
    
        class Trie
        {
            public TrieNode Root = new TrieNode();
    
            public void Insert(string word)
            {
                var cur = Root;
                foreach(var c in word)
                {
                    var index = c - 'a';
                    
                    if (cur.Nodes[index] == null) cur.Nodes[index] = new TrieNode();
    
                    cur = cur.Nodes[index];
                }
                
                cur.Word = word;
                cur.IsFinished = true;
            }
        }
    
        class TrieNode
        {
            public bool IsFinished = false;
            public string Word;
            public TrieNode[] Nodes = new TrieNode[26];
        }
    }
    

Log in to reply
 

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