Leetcode 79. Word Search

Problem

You are given a 2D grid of characters and a target word string. Your task is to determine whether the word can be constructed by following a path through adjacent cells in the grid. Adjacent cells are those connected horizontally or vertically (diagonal connections do not count). Each cell in the grid can only be used once per search path.

Return true if such a path exists, otherwise return false.

Requirements

1. The search must start from any cell in the grid that matches the first character of the word
2. Each subsequent character must be found in a cell adjacent (up, down, left, right) to the previous cell
3. A cell cannot be revisited within the same path
4. The entire word must be matched character by character

Constraints

• m == board.length (number of rows)
• n == board[i].length (number of columns)
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board and word consist of only lowercase and uppercase English letters
• Expected time complexity: O(m * n * 4^L) where L is the length of the word
• Expected space complexity: O(L) for the recursion stack

Examples

Example 1:

Input: board = [['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E']], word = "ABCCED" Output: true Explanation: Starting from A at (0,0), we can trace the path A→B→C→C→E→D

Example 2:

Input: board = [['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E']], word = "SEE" Output: true Explanation: Starting from S at (1,0), we can trace the path S→E→E

Example 3:

Input: board = [['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E']], word = "ABCB" Output: false Explanation: No valid path exists because we would need to reuse cell B

Hint 1: Starting Point You need to try starting the search from every cell in the grid that matches the first character of the word. Use nested loops to iterate through all possible starting positions.

Hint 2: Exploration Strategy Use depth-first search (DFS) with backtracking. From each cell, explore all four adjacent directions recursively. Keep track of which cells have been visited in the current path to avoid reusing them.

Hint 3: State Management You can mark cells as visited by temporarily modifying the board (e.g., changing the character to a special marker) and then restoring it when backtracking. Alternatively, use a separate visited set to track coordinates.

Full Solution `` Approach Explanation:

The solution uses depth-first search (DFS) combined with backtracking to explore all possible paths in the grid:

1. Outer Loop: Iterate through every cell in the grid to find potential starting points (cells matching the first character of the word)

2. DFS Search: From each starting point, recursively explore all four adjacent directions (up, down, left, right)

   • Check if the current cell matches the current character in the word
   • Mark the cell as visited to prevent reuse
   • Recursively search adjacent cells for the next character
   • If a path leads nowhere, backtrack by unmarking the cell

3. Visited Tracking: We modify the board in-place by temporarily replacing visited cells with a special marker ('#'). After exploring from a cell, we restore its original value to allow other paths to use it

4. Early Termination: If we successfully match all characters in the word (index reaches word length), return true immediately

Time Complexity: O(m * n * 4^L) where m and n are the grid dimensions and L is the word length. In the worst case, we start DFS from each cell and explore up to 4 directions at each step.

Space Complexity: O(L) for the recursion call stack, where L is the word length.