Microsoft Question: There exists 2D char array, We need to find out whether a given string("microsoft") exists in the given matrix. the string can be vertical or horizontal..but NOT diagonal

I think it can be achieved with straight forward recursive programming. Following is my solution --

        public bool Exist(char[][] board, string word)

        {

            for (int i = 0; i < board.Length; ++i)

            {

                for (int j = 0; j < board[0].Length; ++j)

                {

                    if (board[i][j] == word[0])

                    {

                        if (this.Search(board, i, j, word, 0))

                        {

                            return true;

                        }

                    }

                }

            }

            return false;

        }

        private bool Search(char[][] board, int i, int j, string word, int currIndex)

        {

            if (currIndex == word.Length)

            {

                return true;

            }

            if (!this.Check(board, i, j, word[currIndex]))

            {

                return false;

            }

            

            char temp = board[i][j];

            board[i][j] = '#';

            bool result = this.Search(board, i - 1, j, word, currIndex + 1) ||

                this.Search(board, i + 1, j, word, currIndex + 1) ||

                this.Search(board, i, j - 1, word, currIndex + 1) ||

                this.Search(board, i, j + 1, word, currIndex + 1);

            board[i][j] = temp;

            return result;

        }

        private bool Check(char[][] board, int i, int j, char ch)

        {

            if (i >= 0 && i < board.Length && j >= 0 && j < board[0].Length && board[i][j] == ch)

                return true;

            return false;

        }