Leetcode 213 - word search algorithm - using Trie, solve timeout

Leetcode213_WordSearch_usingTrie.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode213_AllWordsInBoard_Trie
{
    /// <summary>
    /// Leetcode 212
    /// https://leetcode.com/problems/word-search-ii/#/solutions
    /// 
    /// Study code from the discussion of Leetcode:
    /// https://discuss.leetcode.com/topic/33246/java-15ms-easiest-solution-100-00/2
    /// 
    /// </summary>
    class Leetcode213_AllWordsInBoard_Trie
    {
        /// <summary>
        /// class Trie:
        /// 
        /// </summary>
        internal class TrieNode
        {
            public TrieNode[] Next = new TrieNode[26];
            public String     Word { get; set; }
        }

        static void Main(string[] args)
        {
            string[] words = new string[] { "oath", "pea", "eat", "rain" };

            var board = new char[][]{
                new char[] {'o','a','a','n'},
                new char[] {'e','t','a','e'},
                new char[] {'i','h','k','r'},
                new char[] {'i','f','l','v'}};

            var found = findWords(board, words); 
        }

        public static List<String> findWords(char[][] board, String[] words) {
            var result = new List<string>();
            var root = BuildTrie(words);

            for (int row = 0; row < board.Length; row++) 
            {
                for (int col = 0; col < board[0].Length; col++) 
                {
                    searchWord (board, row, col, root, result);
                }
            }

            return result;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="board"></param>
        /// <param name="row"></param>
        /// <param name="column"></param>
        /// <param name="trie"></param>
        /// <param name="words"></param>
        public static void searchWord(char[][] board, int row, int column, TrieNode trie, List<String> words)
        {
            var visit = board[row][column];

            if (visit == '#' || trie.Next[visit - 'a'] == null)
            {
                return;
            }

            trie = trie.Next[visit - 'a'];

            if (trie.Word != null)
            {   // found one
                words.Add(trie.Word);
                trie.Word = null;     // de-duplicate
            }

            board[row][column] = '#';

            if (row > 0)
            {
                searchWord(board, row - 1, column, trie, words);
            }

            if (column > 0)
            {
                searchWord(board, row, column - 1, trie, words);
            }

            if (row < board.Length - 1)
            {
                searchWord(board, row + 1, column, trie, words);
            }

            if (column < board[0].Length - 1)
            {
                searchWord(board, row, column + 1, trie, words);
            }

            board[row][column] = visit;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="words"></param>
        /// <returns></returns>
        public static TrieNode BuildTrie(String[] words) {
            TrieNode root = new TrieNode();

            foreach (var word in words) 
            {
                var trie = root;
                foreach (var c in word.ToCharArray()) 
                {
                    int current = c - 'a';

                    if (trie.Next[current] == null)
                    {
                        trie.Next[current] = new TrieNode();
                    }

                    trie = trie.Next[current]; // iterate to next 
                }

                trie.Word = word;
            }

            return root;
        }       
    }
}