Problem Description

You are given an m x n grid filled with characters and a string word. Your task is to determine if the word can be found in the grid.

The word can be formed by connecting letters from adjacent cells in the grid, where "adjacent" means cells that share an edge (horizontally or vertically neighboring - not diagonally). You can start from any cell in the grid.

Key constraints:

• Each cell can only be used once in forming the word
• You must move to adjacent cells (up, down, left, or right) to form consecutive letters of the word
• The same cell cannot be revisited within a single word path

For example, if you have a 3x4 grid:

[['A','B','C','E'],
 ['S','F','C','S'],
 ['A','D','E','E']]

And the word is "ABCCED", you can find it by starting at position (0,0) with 'A', then moving right to 'B', right to 'C', down to 'C', down to 'E', and left to 'D'. This would return true.

However, if the word is "ABCB", it would return false because after using the 'B' at position (0,1), you cannot reuse it to form the second 'B' in the word.

The function should return true if the word exists in the grid following these rules, and false otherwise.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The grid can be viewed as a graph where each cell is a node, and edges connect to adjacent cells (up, down, left, right). We need to find a path through this graph that spells out the word.

Is it a tree?

• No: The grid structure is not a tree - it can have cycles and multiple paths between nodes. A cell can be reached from multiple directions.

Is the problem related to directed acyclic graphs?

• No: The grid doesn't have a directed acyclic structure. We can move in any direction (up, down, left, right) and potentially create cycles if we weren't tracking visited cells.

Is the problem related to shortest paths?

• No: We're not looking for the shortest path. We need to find if ANY valid path exists that forms the word.

Does the problem involve connectivity?

• No: We're not checking if components are connected or finding connected components. We're searching for a specific sequence of characters.

Does the problem have small constraints?

• Yes: The grid dimensions are typically small (m × n), and we need to explore paths systematically. The constraint that each cell can only be used once in a path makes this a constrained search problem.

DFS/backtracking?

• Yes: This is the perfect fit. We need to explore paths depth-first, and when a path doesn't work out, we need to backtrack (marking cells as unvisited again) and try alternative paths.

Conclusion: The flowchart suggests using DFS with backtracking for the Word Search problem. This matches the solution approach where we recursively explore each possible path from every starting position, marking cells as visited during exploration and unmarking them when backtracking.

Intuition

Think of this problem like trying to find a specific route on a map where you can only travel to adjacent locations and can't revisit any place you've already been. You're essentially playing a maze game where you need to spell out a word by walking through the grid.

The key insight is that we need to explore all possible paths systematically. When we stand on a cell, we have up to 4 choices for the next move (up, down, left, right). This branching nature of choices naturally leads us to think about recursion - at each step, we try one direction, and if it works, we continue from there; if it doesn't work, we come back and try another direction.

The critical challenge is ensuring we don't use the same cell twice in our path. Imagine leaving breadcrumbs as you walk through the maze - you need to mark where you've been. But here's the clever part: if a path doesn't lead to the complete word, we need to pick up our breadcrumbs so that cell can be used in a different path attempt. This is the essence of backtracking.

Why start from every cell? Because we don't know where the word begins in the grid. Any cell could be the starting point of our word. So we systematically try starting from each cell - if we find the word starting from any position, we're done.

The DFS approach emerges naturally because we want to follow one path completely before trying another. It's like following one branch of possibilities all the way to the end before backing up and trying a different branch. We go as deep as possible (trying to match as many characters as we can), and only when we hit a dead end (wrong character or out of bounds) do we backtrack and try a different route.

The temporary marking strategy (board[i][j] = "0") is our way of saying "I'm currently using this cell" without needing extra space for a visited array. Once we're done exploring from that cell, we restore its original value, allowing it to be used in other path attempts from different starting points.

Learn more about Depth-First Search and Backtracking patterns.

Solution Approach

The solution implements a DFS with backtracking strategy. Let's walk through the implementation step by step:

Main Function Structure: The main function exist() serves as the entry point that tries every cell (i, j) in the grid as a potential starting position. It uses a generator expression with any() to efficiently stop as soon as a valid path is found:

return any(dfs(i, j, 0) for i in range(m) for j in range(n))

DFS Helper Function: The core logic lies in the dfs(i, j, k) function, where:

• i, j represents the current position in the grid
• k represents the index of the character we're currently trying to match in the word

Base Cases:

1. Success Case: If k == len(word) - 1, we've reached the last character. We simply check if the current cell matches this last character:

   if k == len(word) - 1:
       return board[i][j] == word[k]

2. Failure Case: If the current cell doesn't match the expected character, we immediately return False:

   if board[i][j] != word[k]:
       return False

Backtracking Mechanism: The key to preventing cell reuse is the marking strategy:

c = board[i][j]        # Store original character
board[i][j] = "0"      # Mark as visited
# ... explore neighbors ...
board[i][j] = c        # Restore original character (backtrack)

This in-place modification eliminates the need for a separate visited matrix, saving O(m×n) space.

Exploring Neighbors: The code uses an elegant approach with pairwise() to generate direction pairs:

for a, b in pairwise((-1, 0, 1, 0, -1)):
    x, y = i + a, j + b

This creates pairs: (-1, 0), (0, 1), (1, 0), (0, -1) representing up, right, down, and left movements.

For each neighbor, the code:

1. Calculates new coordinates (x, y)
2. Validates boundaries and checks if the cell isn't already visited (not marked as "0")
3. Recursively explores from that position for the next character k + 1
4. Returns True immediately if any direction succeeds (short-circuit evaluation)

Time Complexity: O(m × n × 4^L) where L is the length of the word. We try each cell as a starting point O(m×n), and from each position, we can branch in up to 4 directions for each character.

Space Complexity: O(L) for the recursion stack depth, which can go as deep as the word length. The in-place marking strategy avoids additional space for tracking visited cells.

Example Walkthrough

Let's trace through finding the word "SEE" in this small grid:

[['A','B'],
 ['S','E']]

Step 1: Try starting from (0,0) - 'A'

• Check if 'A' == 'S' (first letter of "SEE")? No, return False
• Move to next starting position

Step 2: Try starting from (0,1) - 'B'

• Check if 'B' == 'S'? No, return False
• Move to next starting position

Step 3: Try starting from (1,0) - 'S'

• Check if 'S' == 'S'? Yes! Continue with DFS
• Mark current cell: board[1][0] = '0' (temporarily)
• Now looking for 'E' (index 1 of "SEE")
• Try neighbors:
  • Up (0,0): 'A' != 'E', fail
  • Right (1,1): 'E' == 'E'! Match found
    • Mark board[1][1] = '0'
    • Now looking for 'E' (index 2 of "SEE")
    • Try neighbors:
      • Up (0,1): 'B' != 'E', fail
      • Right: out of bounds
      • Down: out of bounds
      • Left (1,0): '0' (visited), skip
    • No valid neighbors, backtrack
    • Restore board[1][1] = 'E'
  • Down: out of bounds
  • Left: out of bounds
• All directions failed, backtrack
• Restore board[1][0] = 'S'

Step 4: Try starting from (1,1) - 'E'

• Check if 'E' == 'S'? No, return False

Result: "SEE" cannot be found, return False

Now let's find "SE" in the same grid:

Starting from (1,0) - 'S'

• 'S' == 'S'? Yes!
• Mark board[1][0] = '0'
• Looking for 'E' (index 1, which is last character)
• Try Right (1,1): 'E' == 'E'? Yes!
• Since we've matched the last character, return True

The path S→E successfully spells "SE", so the function returns True.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n × 3^k)

The algorithm iterates through each cell in the m × n grid as a potential starting point, giving us O(m × n) starting positions. For each starting position, we perform a depth-first search (DFS) to find the word.

During the DFS traversal:

• At the first character, we can explore up to 4 directions
• For subsequent characters (positions 2 through k), we can explore at most 3 directions since we mark the current cell as visited (by setting it to "0") and cannot return to it
• The search tree has a maximum depth of k (the word length)
• The branching factor is at most 3 for levels 2 through k

Therefore, the worst-case number of recursive calls from each starting position is O(4 × 3^(k-1)), which simplifies to O(3^k).

Combining with all possible starting positions: O(m × n × 3^k)

Space Complexity: O(min(m × n, k))

The space complexity is determined by the recursion call stack depth. The maximum depth of recursion is bounded by:

• The length of the word k (we stop when we've matched all characters)
• The total number of cells m × n (we can't visit more cells than exist in the grid)

Since the recursion depth cannot exceed either of these limits, the space complexity is O(min(m × n, k)).

Note that the algorithm modifies the board in-place for marking visited cells, so no additional space is needed for tracking visited cells.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Restore the Board State (Backtracking)

One of the most critical pitfalls is failing to properly restore the original character after exploring a path. This permanently corrupts the board and prevents other valid paths from being found.

Incorrect Implementation:

def backtrack(row, col, word_index):
    if word_index == len(word) - 1:
        return board[row][col] == word[word_index]
  
    if board[row][col] != word[word_index]:
        return False
  
    board[row][col] = "#"  # Mark as visited
  
    for delta_row, delta_col in directions:
        next_row = row + delta_row
        next_col = col + delta_col
      
        if (0 <= next_row < rows and 
            0 <= next_col < cols and 
            board[next_row][next_col] != "#"):
          
            if backtrack(next_row, next_col, word_index + 1):
                return True  # ❌ WRONG: Forgot to restore!
  
    # ❌ Missing restoration here too
    return False

Correct Implementation:

def backtrack(row, col, word_index):
    # ... base cases ...
  
    original_char = board[row][col]
    board[row][col] = "#"
  
    for delta_row, delta_col in directions:
        # ... validation ...
        if backtrack(next_row, next_col, word_index + 1):
            board[row][col] = original_char  # ✅ Restore before returning True
            return True
  
    board[row][col] = original_char  # ✅ Always restore before returning False
    return False

2. Using the Visited Marker as a Valid Character

If the visited marker character (like "#" or "0") could potentially appear in the input board, it would cause false negatives.

Problem Example:

board = [['A', '#', 'B']]
word = "A#B"
# If we use '#' as visited marker, we can't distinguish between 
# a visited cell and a cell that actually contains '#'

Solution: Either ensure the marker is outside the valid character set, or use a separate visited set:

def backtrack(row, col, word_index, visited):
    if (row, col) in visited:
        return False
  
    # ... validation ...
  
    visited.add((row, col))
    # ... explore neighbors ...
    visited.remove((row, col))  # Backtrack

3. Early Return Without Restoration

When finding a successful path, forgetting to restore the board before returning can affect subsequent searches if the function is called multiple times.

Problematic Pattern:

for delta_row, delta_col in directions:
    if valid_position and backtrack(next_row, next_col, word_index + 1):
        return True  # ❌ Might forget to restore here

Better Pattern:

found = False
for delta_row, delta_col in directions:
    if valid_position and backtrack(next_row, next_col, word_index + 1):
        found = True
        break

board[row][col] = original_char  # ✅ Always restore
return found

4. Incorrect Boundary Checking Order

Checking array bounds after accessing the array element causes IndexError:

Wrong:

if board[next_row][next_col] != "#" and 0 <= next_row < rows and 0 <= next_col < cols:
    # ❌ Accesses board before checking bounds

Correct:

if 0 <= next_row < rows and 0 <= next_col < cols and board[next_row][next_col] != "#":
    # ✅ Checks bounds first (short-circuit evaluation)

5. Not Handling Edge Cases

Failing to handle edge cases like empty board or empty word:

Robust Implementation:

def exist(self, board: List[List[str]], word: str) -> bool:
    if not board or not board[0] or not word:
        return False if word else True  # Empty word is found in any board
  
    # ... rest of the implementation