[LeetCode] Word Search

Problem: Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true

Constraints:

• m = board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board and word consists of only lowercase and uppercase English letters.

Approach: This problem is same as finding "microsoft" in a 2D matrix. Here we just need to find any string which is given as input. We will use the exactly same backtracking approach which we applied in the previous problem.

Implementation in C#:

    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;

    }

Complexity: O( m * n * 3 ^ l) where m is number of rows, n is number of columns and l is the length of word.