How do you solve Word Search on LeetCode?

Word Search (LeetCode #79) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(m * n * L) time complexity and O(L) space complexity. Key insight: Understanding the grid traversal is crucial; adjacent cells can be explored in four directions.

What is the brute force solution for Word Search?

The brute force approach for Word Search is Brute Force, with O(m * n * 4^L) time complexity and O(L) space complexity. The brute force approach checks every possible path in the grid to see if it can form the target word. This involves exploring all adjacent cells recursively until the word is either found or all options are exhausted. The optimal Optimal Solution approach improves this to O(m * n * L).

What algorithm or data structure is used to solve Word Search?

Word Search uses the following concepts: Array, String, Backtracking, Depth-First Search, Matrix. The recommended patterns to study are: Backtracking, Depth-First Search.

What are the interview tips for Word Search?

Explain your thought process clearly while coding; it helps the interviewer understand your approach. Consider edge cases, such as empty grids or words longer than the total number of cells. Practice writing clean and efficient code, as readability is often evaluated in interviews.

What are common mistakes when solving Word Search?

Failing to handle the boundaries of the grid correctly can lead to index errors. Not unmarking cells after backtracking can cause incorrect results.

#79

Word Search

Medium

ArrayStringBacktrackingDepth-First SearchMatrixBacktrackingDepth-First Search

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(m * n * 4^L)	O(m * n * L)
Space	O(L)	O(L)

💡

Intuition

Time O(m * n * L)Space O(L)

The optimal solution uses the same DFS approach but incorporates pruning techniques to avoid unnecessary searches. By marking cells as visited and unvisited, we prevent revisiting cells in the current path, which optimizes our search.

⚙️

Algorithm

4 steps

1Step 1: Iterate through each cell in the grid.
2Step 2: For each cell, initiate a depth-first search (DFS) to explore possible paths for the word.
3Step 3: If the current character matches the corresponding character in the word, continue the search in adjacent cells while marking the cell as visited.
4Step 4: If the entire word is found, return true; if not, backtrack and unmark the cell.

solution.py26 lines

1# Full working Python code
2class Solution:
3    def exist(self, board, word):
4        if not board:
5            return False
6        rows, cols = len(board), len(board[0])
7        for r in range(rows):
8            for c in range(cols):
9                if self.dfs(board, word, r, c, 0):
10                    return True
11        return False
12    
13    def dfs(self, board, word, r, c, index):
14        if index == len(word):
15            return True
16        if r < 0 or r >= len(board) or c < 0 or c >= len(board[0]) or board[r][c] != word[index]:
17            return False
18        temp = board[r][c]
19        board[r][c] = '#'  # mark as visited
20        found = (self.dfs(board, word, r + 1, c, index + 1) or
21                  self.dfs(board, word, r - 1, c, index + 1) or
22                  self.dfs(board, word, r, c + 1, index + 1) or
23                  self.dfs(board, word, r, c - 1, index + 1))
24        board[r][c] = temp  # unmark
25        return found
26

ℹ

Complexity note: The time complexity is O(m * n * L) where m is the number of rows, n is the number of columns, and L is the length of the word. The space complexity remains O(L) due to the recursion stack.

1Understanding the grid traversal is crucial; adjacent cells can be explored in four directions.
2Marking cells as visited prevents cycles and ensures that each cell is used only once in the current path.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.