Problem Statement
Given an m x n grid of characters board and a string word, return true if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.
Example 1:
-
Input: word="ABCCED", board:
{ 'A', 'B', 'C', 'E' }, { 'S', 'F', 'C', 'S' }, { 'A', 'D', 'E', 'E' } -
Output: true
-
Explanation: The word exists in the board:
-> { 'A', 'B', 'C', 'E' },
-> { 'S', 'F', 'C', 'S' },
-> { 'A', 'D', 'E', 'E' }
Example 2:
-
Input: word="SEE", board:
{ 'A', 'B', 'C', 'E' }, { 'S', 'F', 'C', 'S' }, { 'A', 'D', 'E', 'E' } -
Output: true
-
Explanation: The word exists in the board:
-> { 'A', 'B', 'C', 'E' },
-> { 'S', 'F', 'C', 'S' },
-> { 'A', 'D', 'E', 'E' }
Constraints:
m == board.lengthn = board[i].length1 <= m, n <= 61 <= word.length <= 15boardandwordconsists of only lowercase and uppercase English letters.
Why this is a Backtracking problem
| What the question says | The signal it matches |
|---|---|
| "return true if the word exists in the grid" | you need one valid answer out of many arrangements |
| "letters of sequentially adjacent cells" | each step is a choice of direction |
| "The same letter cell may not be used more than once" | a partial answer can be ruled out early |
This is the choose a direction on a grid variant: step to a neighbouring cell, and stop when the letter does not match.
The closest alternative. The Island pattern, since this is a grid walk. It does not fit. Island problems explore a whole region and never revisit a cell. Here a cell used on one attempt must become free again when that attempt fails.
That difference is the undo step, and the introduction warns it is the easiest thing to forget. Mark the cell as used before stepping deeper, and unmark it on the way back out. Forget the unmark and the search reports too few answers, because cells stay blocked for paths that never used them. The pruning is the letter check: if the current cell does not match the next letter of the word, the branch ends immediately.
Solution
The basic approach to solving the word search problem using backtracking is to start at the first character of the word and check all 4 adjacent cells in the grid to see if any of them match the next character of the word. If a match is found, mark the cell as visited and recursively check the next character of the word in the adjacent cells of the newly visited cell. If the entire word is found, return true. If no match is found, backtrack to the previous cell and try a different path. Repeat this process until the entire grid has been searched or the word is found.
Algorithm Walkthrough
Let's trace the second example, word = "SEE" on the same board. Move through the steps one at a time:
Step 1. The word "SEE" has to be spelled by stepping between neighbouring cells, never reusing one. Two cells on the board hold an S, so there are two places the search can begin. Backtracking means going as far as possible down one choice, and when it fails, undoing the last step and trying the next option rather than starting over.
1 of 5
Code
This function takes a 2D list board and a string word as input, and returns True if the word can be found in board and False otherwise. It uses a helper function dfs which takes 4 additional parameters: i and j are the current coordinates of the cell that is being visited, k is the index of the current character of the word being matched, and board and word are the inputs passed to the main function.
The dfs function uses a helper variable tmp to store the current value of the cell before it is marked as visited. This is done so that we can backtrack later. It then uses recursion to check if the next character of the word exists in the 4 adjacent cells, and it will mark the cell as visited and move to next index of the word by incrementing k by 1. If the next character is found, the function returns true, if not it backtracks to the previous cell, and continues the search in different path. If the entire word is found, the function returns True, otherwise it returns False after searching the entire grid.
Time Complexity
The overall time complexity of the algorithm is O(M \cdot N \cdot 4^L)
- (M \cdot N): Number of cells in the board.
- (4^L): Each cell can lead to up to 4 recursive calls (one for each direction: up, down, left, right). For a word of length (L), there are up to (4^L): possible paths to explore.
Thus, for each cell, the DFS can potentially explore (4^L): paths. Since the search starts from every cell, the overall complexity is O(M \cdot N \cdot 4^L).
A tighter figure is O(M * N * 3^L). Only the very first step has four directions to choose from. After that, the cell you came from is marked as visited, so each later step has at most three. The difference does not change the shape of the answer and it is worth saying, because it shows you have thought about what the marking buys.
Space Complexity
The space complexity of the exist function is O(n), where n is the length of the word. This is because the function uses a DFS algorithm, and the maximum depth of the recursion tree is n. In other words, the maximum number of function calls that will be stored on the call stack at any point in time is n.