LeetCode Solution 79 - Word Search

 Problem Statement

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

---

Optimal Approach

The optimal solution to this problem is Backtracking with DFS (Depth First Search). We will explore each cell in the grid and check if the word can be formed using a recursive search while ensuring that we do not use any cell more than once.

Algorithm:

1. Iterate through each cell of the board.
2. If the first letter of the word matches the cell, perform a DFS search.
3. In DFS, mark the current cell as visited to avoid reuse.
4. Recursively search in all four directions (up, down, left, right).
5. If at any point the word is completely found, return true.
6. Backtrack (unmark the visited cell) and continue searching.
7. If no valid path is found, return false.

---

C++ Code Implementation (LeetCode-Compatible)

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int rows = board.size();
        int cols = board[0].size();
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (board[i][j] == word[0] && dfs(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }
    
private:
    bool dfs(vector<vector<char>>& board, string& word, int i, int j, int index) {
        if (index == word.size()) return true;
        
        if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || board[i][j] != word[index]) {
            return false;
        }
        
        char temp = board[i][j];
        board[i][j] = '#'; // Mark as visited
        
        bool found = dfs(board, word, i + 1, j, index + 1) ||
                     dfs(board, word, i - 1, j, index + 1) ||
                     dfs(board, word, i, j + 1, index + 1) ||
                     dfs(board, word, i, j - 1, index + 1);
        
        board[i][j] = temp; // Unmark
        return found;
    }
};

---

Step-by-Step Explanation

1. Iterate through the board: Check each cell to see if it matches the first character of the word.
2. Call DFS recursively: Explore adjacent cells in four directions (up, down, left, right).
3. Mark visited cells: Replace the character with # to prevent revisiting the same cell.
4. Backtracking: If the path is incorrect, revert changes and try another direction.
5. Return true if found: Stop as soon as the full word is matched.

---

Dry Run with Example

Input:

board = [["A","B","C","E"],
         ["S","F","C","S"],
         ["A","D","E","E"]]
word = "ABCCED"

Execution:

1. Start at board[0][0] = 'A', matches first character.
2. Move to board[0][1] = 'B', matches next character.
3. Move to board[0][2] = 'C', matches next character.
4. Move to board[1][2] = 'C', matches next character.
5. Move to board[1][1] = 'E', matches next character.
6. Move to board[2][1] = 'D', matches last character.
7. Word is found → return true.

---

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Why Not Optimal?
Brute Force	O((m*n)*4^L)	O(1)	Extremely slow, explores all possibilities blindly.
Trie + Backtracking	O(mnL)	O(m*n)	Useful for multiple searches but adds extra space.

Why Backtracking DFS is Best?

• Efficiently explores valid paths.
• Avoids redundant computation.
• Uses only O(L) space (recursive depth), where L is the word length.

---

Complexity Analysis

• Time Complexity: O((m*n)*4^L) (worst case where L is the word length)
• Space Complexity: O(L) (recursive call stack depth)

---

Conclusion

• Best Approach: Backtracking with DFS.
• Why? Minimal space usage and efficient pruning of invalid paths.
• Similar Problems:
  • 79. Word Search (this problem)
  • 212. Word Search II (extended version with multiple words)
  • 200. Number of Islands (similar DFS-based problem)

For more LeetCode solutions, check out our Algorithm Series.