Leetcode 212 - word search II - warm up the optimal solution using Trie data structure and also use recursive function

Leetcode212_wordSearchII_warmup.cs

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

namespace Leetcode212_AllWordsInBoard_Trie
{
    /// <summary>
    /// June 14, 2017 
    /// 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 Leetcode212_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)
        {
            RunTestcase(); 
            //RunTestcaseBuildTrie(); 
        }

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

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

            var found = findWords(board, words);
        }

        /// <summary>
        /// code review July 25, 2017
        /// Understand why trie is much better on time complexity 
        /// every word sharing same prefix will be visited once
        /// a
        /// |
        /// a
        /// |
        /// a          "aaa"
        /// | \  \
        /// a  b  c    "aaaa", "aaab", "aaac"
        /// </summary>
        public static void RunTestcaseBuildTrie()
        {
            string[] words = new string[] { "aaa", "aaaa", "aaab", "aaac" };

            var trie = BuildTrie(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.GetLength(0); row++)
            {
                for (int col = 0; col < board.GetLength(1); col++)
                {
                    searchWord(board, row, col, root, result);
                }
            }

            return result;
        }

        /// <summary>
        /// code review on July 25, 2017
        /// It is a warmup process. 
        /// A little surprise of design:
        /// 1. Trie will be updated if the word is found. The word will be removed from 
        /// Trie in order to avoid adding more than once. 
        /// 2. The depth first search technique:
        /// mark the visit node as '#' in order to avoid looping;
        /// back tracking is used;
        /// this code is best template code for depth first search writing. 
        /// So Julia likes to memorize the code. 
        /// </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)
        {
            if ( row    < 0 || row    > (board.GetLength(0) - 1) ||
                 column < 0 || column > (board.GetLength(1) - 1))
            {
                return;
            }

            var visit = board[row, column];

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

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

            if (trie.Word != null)  // the word is found, need to add to result 
            {
                words.Add(trie.Word);

                // avoid the same word to be added more than once 
                // it is not a good design, update trie without telling
                trie.Word = null;     // deduplicate
            }

            // mark the node value with '#', so it will not match any char
            // avoid dead loop, mark visited in depth first search
            // remember this technique
            board[row, column] = '#'; 
            
            searchWord(board, row - 1, column,     trie, words);                                   
            searchWord(board, row,     column - 1, trie, words);                       
            searchWord(board, row + 1, column,     trie, words);                                   
            searchWord(board, row,     column + 1, trie, words);            

            board[row, column] = visit;  // backtracking with DFS search
        }

        /// <summary>
        /// code review on July 25, 2017
        /// Trie is designed with 26 children, if it is the leaf node then
        /// the word is added. 
        /// </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 
                }

                // reach the leaf node of trie - add word string
                trie.Word = word;
            }

            return root;
        }
    }
}