22.Word Search

Given an m x n board and a word, find if the 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 1:

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

Example 2:

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

Example 3:

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

Solution: (DFS)

Iterate through the grid looking for the first character in the desired word. If you find it, call a dfs function to continue looking for the remainder of the letters.

class Solution
{
public:
    bool dfs(vector<vector<char>> &board, string word, int i, int j, int idx)
    {

        if (idx == word.length())
        {
            return true;
        }

        if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || board[i][j] != word[idx])
        {
            return false;
        }

        char temp = board[i][j];
        board[i][j] = ' ';
        

        if (dfs(board, word, i + 1, j, idx + 1))
        {
            return true;
        }

        if (dfs(board, word, i - 1, j, idx + 1))
        {
            return true;
        }

        if (dfs(board, word, i, j + 1, idx + 1))
        {
            return true;
        }

        if (dfs(board, word, i, j - 1, idx + 1))
        {
            return true;
        }

        board[i][j] = temp;

        return false;
    }

    bool exist(vector<vector<char>> &board, string word)
    {
        for (int i = 0; i < board.size(); i++)
        {
            for (int j = 0; j < board[i].size(); j++)
            {

                if (word[0] == board[i][j])
                {
                    if (dfs(board, word, i, j, 0))
                    {
                        return true;
                    }
                }
            }
        }
        return false;
    }
};

Time Complexity: O(n * m) Space Complexity: O(n * m)