C++: Word Search

Thought Process

The solution uses DFS backtracking to search for the word in the 2D board. We start from each cell and explore all four possible directions ( up, down, left, right). A visited matrix tracks which cells we've already checked to avoid cycles. The key optimization is early termination i.e. we stop searching as soon as we find the word. For each character match, we recursively check the next character until we either find the complete word or exhaust all possibilities. 

class Solution {
public:
    bool isExist = false;

    void dfs(vector<vector<char>>& board, vector<vector<int>>& vis, int i,
                int j, string word, int idx) {

        if (i >= board.size() || j >= board[0].size() || i < 0 || j < 0 ||
            word[idx] != board[i][j] || isExist == true || vis[i][j] == true)
            return;

        if (idx == word.size() - 1) {
            isExist = true;
            return;
        }

        vis[i][j] = true;
        dfs(board, vis, i + 1, j, word, idx + 1);
        dfs(board, vis, i - 1, j, word, idx + 1);
        dfs(board, vis, i, j + 1, word, idx + 1);
        dfs(board, vis, i, j - 1, word, idx + 1);
        vis[i][j] = false;
    }
    bool exist(vector<vector<char>>& board, string word) {

        int row = board.size();
        int col = board[0].size();

        // Initialzing the all elements of visited array as false.
        vector<vector<int>> vis(row, vector<int>(col, false));
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++)
                vis[i][j] = false;
        }

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {

                if (!vis[i][j])
                    dfs(board, vis, i, j, word, 0);
            }
        }
        return isExist;
    }
};

Code Complexity

Time Complexity: O(m*n*4^L)

Where m and n are board dimensions and L is word length. In worst case, we explore 4 directions at each step for L steps.

Space Complexity: O(m*n + L)

For the visited matrix (m*n) and recursion stack (L) where L is the word length.

Code copied!