#79

Medium

auto_awesomeBacktracking search with pruning

LeetCode Problem Workspace

Word Search

Solve Word Search with backtracking by exploring adjacent cells to match a target word in a grid.

array string backtracking depth first search matrix

Problem Statement

Given an m x n grid of characters and a string word, you need to determine if the word can be constructed from sequentially adjacent cells. These cells must be horizontally or vertically adjacent. The same cell may not be used more than once during the word construction.

The problem involves searching through the grid, applying backtracking to explore potential paths for forming the target word. Once a valid path is found, the search stops, returning true. If no valid path is found after checking all possibilities, return false.

Examples

Example 1

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

Output: true

Example details omitted.

Example 2

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

Output: true

Example details omitted.

Example 3

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

Output: false

Example details omitted.

Constraints

m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board and word consists of only lowercase and uppercase English letters.

Solution Approach

Backtracking Search

The solution begins by iterating through each cell in the grid. From each starting cell, attempt to match the word by recursively exploring adjacent cells (up, down, left, right). Mark cells as visited during recursion to prevent revisiting. If a character matches and all characters of the word are found, return true. If no solution is found, backtrack to explore other possibilities.

Pruning Unnecessary Searches

Pruning is essential for optimizing performance. If a character doesn't match the target word at a certain cell, or if the number of remaining characters in the word is too large to fit within the grid boundaries, terminate the current recursive search. This reduces the number of paths explored, ensuring that only valid searches are pursued.

Edge Case Handling

Consider scenarios like when the word is larger than the grid or when the word can't be formed from any of the starting positions. Handle the cases where the word exists only if a precise sequence of adjacent cells is matched. Ensure that invalid paths (out of bounds or revisiting cells) are properly handled.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this approach is O(m * n * 4^k), where m and n are the dimensions of the grid, and k is the length of the word. This is because each cell can potentially lead to 4 recursive calls, and the depth of recursion is limited by the word length. Space complexity is O(m * n) for the recursive call stack and visited cell tracking.

What Interviewers Usually Probe

Do you know how to implement backtracking to solve problems like Word Search?
Can you explain the role of pruning in reducing the complexity of backtracking?
Will you consider edge cases like grid boundaries and revisited cells in your solution?

Common Pitfalls or Variants

Common pitfalls

Forgetting to mark cells as visited during recursion, causing incorrect word matches.
Not pruning invalid paths early enough, leading to unnecessary and time-consuming searches.
Overlooking the case where the word exceeds the grid's size or cannot be constructed from adjacent cells.

Follow-up variants

Can you solve Word Search for larger grids (e.g., 10x10)?
How would you handle a grid containing multiple occurrences of the target word?
What if the board was a 2D matrix containing numbers instead of letters?

FAQ

What is the primary pattern used to solve the Word Search problem?

The primary pattern is backtracking search with pruning. By recursively exploring each cell and marking visited ones, unnecessary paths are eliminated.

How do you optimize the backtracking solution for Word Search?

Optimization comes from pruning invalid paths early, avoiding unnecessary recursion calls when a cell is out of bounds or the characters don’t match.

What are some common mistakes when solving Word Search using backtracking?

Common mistakes include failing to mark cells as visited or not handling edge cases like grid boundaries and revisiting cells.

Can the Word Search problem be solved iteratively?

While backtracking is the most natural solution for Word Search, it could be adapted to an iterative approach using a stack, but it would be less efficient.

What edge cases should be considered for Word Search?

Edge cases include when the word is longer than the grid, when no valid path exists, and when certain cells should not be revisited.

terminal

Solution

Solution 1: DFS (Backtracking)

We can enumerate each position $(i, j)$ in the grid as the starting point of the search, and then start a depth-first search from the starting point. If we can search to the end of the word, it means the word exists, otherwise, it means the word does not exist.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(i: int, j: int, k: int) -> bool:
            if k == len(word) - 1:
                return board[i][j] == word[k]
            if board[i][j] != word[k]:
                return False
            c = board[i][j]
            board[i][j] = "0"
            for a, b in pairwise((-1, 0, 1, 0, -1)):
                x, y = i + a, j + b
                ok = 0 <= x < m and 0 <= y < n and board[x][y] != "0"
                if ok and dfs(x, y, k + 1):
                    return True
            board[i][j] = c
            return False

        m, n = len(board), len(board[0])
        return any(dfs(i, j, 0) for i in range(m) for j in range(n))

Continue Practicing

#212 word search ii #37 sudoku solver #130 surrounded regions