C# Trie + DFS Solution


  • 0
    K

    We want to first map all the words into a trie. After that, we DFS on all positions in the board (all the possible start positions) with a root trie node. Every time during a DFS, we check if one of the 4 positions we moved results in the trie node moving to a valid character as well. If the trie node holds a word, then add that as a solution.

    public class Solution {
        public IList<string> FindWords(char[,] board, string[] words) {
            IList<string> list = new List<string>();
            bool[,] visited = new bool[board.GetLength(0), board.GetLength(1)];
            TrieNode root = buildTrie(words);
            
            for(int i = 0; i < board.GetLength(0); ++i){
                for(int j = 0; j < board.GetLength(1); ++j){
                    Helper(board, i, j, visited, root, list);
                }   
            }
            
            return list;
        }
        
        private void Helper(char[,] board, int row, int col, bool[,] visited, TrieNode node, IList<string> list) {
            if(row >= board.GetLength(0) || row < 0 || col >= board.GetLength(1) || col < 0) {
                return;
            }
            if (visited[row, col]) {
                return;
            }
            
            char c = board[row, col];
            node = node.next[c - 'a'];
            if(node == null) {
                return;
            }
            
            if(node.word != null) {
                list.Add(node.word);
                node.word = null;
            }
                    
            visited[row, col] = true;
            
            Helper(board, row + 1, col, visited, node, list);
            Helper(board, row - 1, col, visited, node, list);
            Helper(board, row, col + 1, visited, node, list);
            Helper(board, row, col - 1, visited, node, list);
            
            visited[row, col] = false;
        }
        
        private TrieNode buildTrie(string[] words) {
            TrieNode root = new TrieNode();
            foreach(string word in words){
                TrieNode curr = root;
                foreach(char c in word){
                    if(curr.next[c - 'a'] == null) {
                        curr.next[c - 'a'] = new TrieNode();
                    }
                    curr = curr.next[c - 'a'];
                }
                curr.word = word;
            }
            return root;
        }    
    }
    
    public class TrieNode {
        public TrieNode[] next = new TrieNode[26];
        public string word;
    }
    

Log in to reply
 

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