Leetcode 212 - word search II - pass online judge - learn how to design a trie, and idea to solve the time out using trie.

Leetcode212_WordSearchII.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)
        {
            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); 
        }

        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>
        /// 
        /// </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)  // the word is found, need to add to result 
            {   
                words.Add(trie.Word);

                // avoid to be added more than once 
                trie.Word = null;     // deduplicate
            }

            board[row, column] = '#'; // mark the node value with '#', so it will not match any char

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

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

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

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

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

        /// <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 
                }

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

            return root;
        }       
    }
}