79. Word Search

Problem Description

The problem gives us a 2D grid of characters called board and a string word. Our task is to determine if word exists in the grid. A word is said to exist in the grid if it can be formed by tracing a path through adjacent cells. Cells are considered adjacent if they are directly above, below, to the left, or to the right of one another (diagonal adjacency is not allowed). As we trace the path to form the word, we cannot use the same cell more than once. The goal is to return true if the word can be constructed from the grid following these rules, otherwise, we return false.

Intuition

To solve this problem, we employ a technique known as Depth-First Search (DFS). The intuition behind using DFS is that it allows us to explore all potential paths from a starting cell to see if we can spell out the word.

Here's the thinking process for arriving at the DFS solution approach:

Start at Every Cell: We need to consider every cell in the grid as a potential starting point of our word.
Explore Adjacent Cells: Once we've picked a starting cell, we look at its adjacent cells. If the current cell contains the correct letter (the next letter in word that we're looking for), we can move onto this adjacent cell.
Track Where We've Been: In order not to use the same cell twice, we temporarily modify the current cell in the grid to mark it as 'visited'. This way, we avoid re-visiting cells on the current path. It's important to remember to reset this cell back to its original state after we finish searching from that cell.
Use Recursion for Simplicity: Implementing our DFS as a recursive function is convenient because it allows us to easily backtrack (undo our choice of the current letter and try a different path) if we realize we can't spell out the entire word from the current path.
Termination Conditions: The DFS should terminate when we have successfully found the last letter of word, or when we have run out of valid paths to pursue. In the first case, we immediately return true, and in the second case, once all possibilities have been exhausted from a certain cell, we return false.

Writing this logic into a recursive function dfs, we're able to perform a thorough search from each starting cell until we find a path that matches word. By using the function any(), we execute our DFS starting from each cell and return true as soon as at least one call to dfs returns true.

The function pairwise() used in the code appears to be a utility that generates pair-wise combinations of provided elements, but it's not part of standard Python libraries as of the last update and might be custom-defined. It is effectively being used to iterate through the possible adjacent cells coordinates with respect to the current cell.

Learn more about Backtracking patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x1 2 3 x x x 6 x x1 2 6 x x x 3 x x

I don’t know

Solution Approach

The solution utilizes a recursive Depth-First Search (DFS) algorithm to navigate through the board. Let's walk through the key components of the implementation.

Base Case

Each recursive dfs call has a base case that compares the length of the word we're looking for with the index k:

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

This condition checks if we've reached the end of the word. If so, we compare the current cell's character with the last character of the word. If they match, it means we've successfully found word in the board.

Current Letter Match Check

Before diving deeper, we ensure that the current cell's character matches the current letter in word we're looking for:

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

If it doesn't match, there's no point in continuing from this cell, so we return False.

Avoiding Re-use of the Same Cell

To avoid revisiting the same cell, the solution marks the cell with a placeholder "0":

1c = board[i][j]
2board[i][j] = "0"

After the placeholder assignment, DFS exploration continues, and once done, the cell is reset to its original state:

1board[i][j] = c

Exploring Adjacent Cells

To navigate through adjacent cells, we use a loop that iterates through coordinate offsets. Instead of a standard for loop, it uses pairwise() combined with a tuple (-1, 0, 1, 0, -1) to generate the pairs of offsets representing up, right, down, and left moves:

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

The move is valid if it's within the bounds of the grid and the cell has not been visited (marked as '0'):

1ok = 0 <= x < m and 0 <= y < n and board[x][y] != "0"

If the move is valid, the dfs is called recursively for the next cell with the index k + 1 to check the following character in the word:

1if ok and dfs(x, y, k + 1):
2    return True

Kickstarting DFS and Returning Result

The dfs function is invoked for each cell in the grid by using a combination of any() and a nested for loop, which iterates through each cell's indices (i, j):

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

The search terminates and returns true as soon as any starting cell leads to a successful dfs exploration that finds the word.

By employing a recursive approach, the solution ensures that all possible paths are explored from each starting cell, without revisiting cells and without departing from the constraints defined by the problem—namely the adjacency restriction and the uniqueness of the path's cells.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Example Walkthrough

Let's demonstrate how the Depth-First Search (DFS) solution method works using a simplified example.

Imagine we have the following grid and word:

1board = [
2    ['A', 'B', 'C', 'E'],
3    ['S', 'F', 'C', 'S'],
4    ['A', 'D', 'E', 'E']
5]
6word = "SEE"

We want to know whether we can find the word "SEE" in the grid by moving to adjacent cells without reusing any cell.

Start at Every Cell: We initiate our DFS from board[0][0] with A. Since A is not S (the first letter of "SEE"), the search does not continue from here. Next, we try board[0][1] which is B, again not matching 'S'. We continue this process until we find S at board[1][0].
Explore Adjacent Cells: From board[1][0] (which is S), we look at the adjacent cells (board[0][0], board[1][1], board[2][0] and board[1][0] as vowel cells are not considered).
Track Where We've Been: We mark board[1][0] as visited by setting it to "0".
Use Recursion for Simplicity: We start a recursive call from board[1][1] where we find F—not the correct letter, so the call returns False, and we continue the DFS.
Termination Conditions: Continuing the search, board[2][0] is A (also not E), so we move on to board[2][1] (which is D), and finally to board[2][2] which is E - this matches the second letter of "SEE".
The next recursive call starts from board[2][2], and we mark it visited. Its adjacent cells (excluding the one we just came from and marked ones) are checked. board[2][3] is E—the last letter we're looking for.
The base case is met (we are at the last letter of the word), and since board[2][3] matches the last letter of "SEE", the recursive call returns True.
We backtrack, unmarking the visited cells, and propagate the True value upwards through the recursion stack, ultimately return True from the initial call.
Since we've found at least one path that spells "SEE", we can stop the search and return True. No need to check further cells.

Here's a visual representation of the path that spells "SEE":

1[ ]
2[S]
3[E]
4[E]

Using this approach, we verify that "SEE" exists within the board as per the rules given, and the function would return True.

Solution Implementation

1class Solution:
2    def exist(self, board: List[List[str]], word: str) -> bool:
3        # Depth-first search function to search the word in the board
4        def search_word(x: int, y: int, index: int) -> bool:
5            # Check if the last character matches 
6            if index == len(word) - 1:
7                return board[x][y] == word[index]
8            # If current character does not match the word character at index, return False
9            if board[x][y] != word[index]:
10                return False
11            # Store the current character and mark the cell as visited with "0"
12            temp = board[x][y]
13            board[x][y] = "0"
14            # Define directions for exploration: up, right, down, left
15            directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
16            # Loop through all possible directions
17            for dx, dy in directions:
18                new_x, new_y = x + dx, y + dy
19                # Check boundaries and if the next cell is not visited
20                if 0 <= new_x < rows and 0 <= new_y < cols and board[new_x][new_y] != "0":
21                    # Recur with the new position and the next character index
22                    if search_word(new_x, new_y, index + 1):
23                        return True
24            # Restore the current cell's value after exploring all directions
25            board[x][y] = temp
26            return False
27
28        # Retrieve the dimensions of the board
29        rows, cols = len(board), len(board[0])
30        # Iterate through each cell in the board, trying to match the first character
31        for i in range(rows):
32            for j in range(cols):
33                # If the first character matches and the word can be found from here, return True
34                if board[i][j] == word[0] and search_word(i, j, 0):
35                    return True
36        # If the word cannot be found, return False
37        return False
38```
39
40Please note that you should replace `List` with `list` and add the required import statements if you are directly running this code in a Python environment. The `List` type hint notation assumes you have the appropriate import from the `typing` module:
41
42```python
43from typing import List
44

1class Solution {
2    // Class level variables to hold the dimensions of the board, the word, and the board itself
3    private int rows;
4    private int cols;
5    private String targetWord;
6    private char[][] gameBoard;
7
8    // Method to determine if the target word exists in the board
9    public boolean exist(char[][] board, String word) {
10        rows = board.length;       // Number of rows in the board
11        cols = board[0].length;    // Number of columns in the board
12        targetWord = word;         // The word we are searching for
13        gameBoard = board;         // The game board
14      
15        // Iterate over every cell in the board
16        for (int i = 0; i < rows; ++i) {
17            for (int j = 0; j < cols; ++j) {
18                // If the first letter matches and dfs search is successful, return true
19                if (dfs(i, j, 0)) {
20                    return true;
21                }
22            }
23        }
24      
25        // If we have not returned true at this point, the word does not exist in the board
26        return false;
27    }
28
29    // Helper method to perform Depth First Search (DFS)
30    private boolean dfs(int row, int col, int index) {
31        // Check if we are at the last character of the word
32        if (index == targetWord.length() - 1) {
33            return gameBoard[row][col] == targetWord.charAt(index);
34        }
35      
36        // Check if current cell does not match the character at index in word
37        if (gameBoard[row][col] != targetWord.charAt(index)) {
38            return false;
39        }
40      
41        // Temporarily mark the current cell as visited by replacing its value
42        char tempChar = gameBoard[row][col];
43        gameBoard[row][col] = '0';
44      
45        // Define an array of directions (up, right, down, left)
46        int[] directions = {-1, 0, 1, 0, -1};
47      
48        // Explore all possible adjacent cells (up, right, down, left)
49        for (int d = 0; d < 4; ++d) {
50            int newRow = row + directions[d];
51            int newCol = col + directions[d + 1];
52          
53            // Check if the new position is within bounds and not visited
54            if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && gameBoard[newRow][newCol] != '0') {
55                // If the dfs search from the adjacent cell is successful, return true
56                if (dfs(newRow, newCol, index + 1)) {
57                    return true;
58                }
59            }
60        }
61      
62        // Reset the cell's value back from '0' to its original character
63        gameBoard[row][col] = tempChar;
64      
65        // If none of the adjacent cells leads to a solution, return false
66        return false;
67    }
68}
69

1#include <vector>
2#include <string>
3#include <functional>
4
5class Solution {
6public:
7    // Function to check if the word exists in the given 2D board
8    // by performing a depth-first search (DFS)
9    bool exist(vector<vector<char>>& board, string word) {
10        int rowCount = board.size();          // Number of rows in the board
11        int colCount = board[0].size();      // Number of columns in the board
12        // Directions for exploring adjacent cells (up, right, down, left)
13        int directions[5] = {-1, 0, 1, 0, -1};
14
15        // Recursive lambda function for performing DFS
16        function<bool(int, int, int)> dfs = [&](int row, int col, int wordIndex) -> bool {
17            if (wordIndex == word.size() - 1) {
18                // If we are at the last character, check if it matches
19                return board[row][col] == word[wordIndex];
20            }
21            if (board[row][col] != word[wordIndex]) {
22                // If the current character does not match, return false
23                return false;
24            }
25            char tempChar = board[row][col];   // Temporarily store the current character
26            board[row][col] = '0';             // Mark the cell as visited by placing a '0'
27
28            // Explore the adjacent cells in all four directions
29            for (int dir = 0; dir < 4; ++dir) {
30                int newRow = row + directions[dir], newCol = col + directions[dir + 1];
31                // Check if the new position is within the board and not visited
32                if (newRow >= 0 && newRow < rowCount && 
33                    newCol >= 0 && newCol < colCount && 
34                    board[newRow][newCol] != '0' && 
35                    dfs(newRow, newCol, wordIndex + 1)) {
36                        return true;    // If able to complete the word from this position, return true
37                }
38            }
39
40            board[row][col] = tempChar;       // Reset the cell back to its original character
41            return false;                      // If unable to complete the word, return false
42        };
43
44        // Iterate over each cell in the 2D board
45        for (int i = 0; i < rowCount; ++i) {
46            for (int j = 0; j < colCount; ++j) {
47                // Start DFS from this cell if it matches the first character of the word
48                if (dfs(i, j, 0)) {
49                    return true;
50                }
51            }
52        }
53        return false; // Return false if the word is not found
54    }
55};
56

1function exists(board: string[][], word: string): boolean {
2    // Get the dimensions of the board
3    const rows = board.length;
4    const cols = board[0].length;
5
6    // Directions array to assist in exploring all 4 adjacent cells (up, right, down, left)
7    const directions = [-1, 0, 1, 0, -1];
8
9    // Depth-first search function to explore the board
10    const depthFirstSearch = (row: number, col: number, index: number): boolean => {
11        // Base case: when the last character matches, return true
12        if (index === word.length - 1) {
13            return board[row][col] === word[index];
14        }
15      
16        // If the current character does not match, return false
17        if (board[row][col] !== word[index]) {
18            return false;
19        }
20      
21        // Temporarily mark the board cell to avoid revisiting
22        const tempChar = board[row][col];
23        board[row][col] = '0';
24
25        // Explore all 4 directions from the current cell
26        for (let d = 0; d < 4; ++d) {
27            const nextRow = row + directions[d];
28            const nextCol = col + directions[d + 1];
29
30            // Check if the next cell is within the bounds of the board
31            const isInBounds = nextRow >= 0 && nextRow < rows && nextCol >= 0 && nextCol < cols;
32
33            // If the next cell is valid and the DFS from that cell is successful, return true
34            if (isInBounds && board[nextRow][nextCol] !== '0' && depthFirstSearch(nextRow, nextCol, index + 1)) {
35                return true;
36            }
37        }
38
39        // Restore the cell's original character after exploring
40        board[row][col] = tempChar;
41
42        // If no path was found, return false
43        return false;
44    };
45
46    // Iterate over every cell in the board to see if a word path starts from there
47    for (let row = 0; row < rows; ++row) {
48        for (let col = 0; col < cols; ++col) {
49            if (depthFirstSearch(row, col, 0)) {
50                // If a successful path is found, return true
51                return true;
52            }
53        }
54    }
55
56    // If no successful path was found in the entire board, return false
57    return false;
58}
59

Not Sure What to Study? Take the 2-min Quiz：

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

It's fasterIt has better space complexityOrder of computer subproblems does not matterIt has better time complexity

I don’t know

Time and Space Complexity

Time Complexity

The time complexity of the given code depends on the dimensions of the board (m x n) and the length of the word to be found (l).

The exist method involves iterating over each element in the board to start a depth-first search (DFS). This introduces a factor of m*n.
For every element (i, j), we are potentially doing a DFS. The maximum depth of the DFS is the length of the word l, because we are searching for the word and we return either when we find the whole word or cannot proceed further.
In each DFS call, we check all four directions (up, down, left, and right). However, since we replace the current character with "0" to mark it as visited, every recursive call will have at most 3 unvisited neighbors to explore. This results in 3^(l-1) for the DFS branching factor, as the first call has 4 directions and subsequent calls have only 3 directions because the previous position wouldn't be considered.

So, the worst-case time complexity is O(m*n*3^(l-1)), where m is the number of rows in the board, n is the number of columns in the board, and l is the length of the word.

Space Complexity

The space complexity also has two main contributors:

The recursive call stack due to DFS. In the worst case, the recursion goes as deep as the length of the word l, so the call stack can grow up to O(l).
We are modifying the board in place to mark visited elements, hence not using any additional space proportional to the size of the board (m*n), except for the space used by the call stack.

Considering that, the total space complexity is O(l) due to the recursion call stack, which depends on the length of the word being searched for.

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

Fast Track Your Learning with Our Quick Skills Quiz:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Optimal substructureOverlapping subproblemsNon-overlapping subproblemsConstant time subproblems

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

79. Word Search

Problem Description

Intuition

Solution Approach

Base Case

Current Letter Match Check

Avoiding Re-use of the Same Cell

Exploring Adjacent Cells

Kickstarting DFS and Returning Result

Example Walkthrough

Solution Implementation