Problem
Given an m x n
grid of characters board
and a string word
, return true
if 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
Example 1:
$$ \Huge \begin{array}{|c|c|c|c|} \hline \colorbox{YellowOrange} A & \colorbox{YellowOrange} B & \colorbox{YellowOrange} C & E \\ \hline S & F & \colorbox{YellowOrange} C & S \\ \hline A & \colorbox{YellowOrange} D & \colorbox{YellowOrange} E & E \\ \hline \end{array}
$$
|
|
Example 2:
$$ \Huge \require{xcolor} \begin{array}{|c|c|c|c|} \hline A & B & C & E \\ \hline S & F & C & \colorbox{YellowOrange} S \\ \hline A & D & \colorbox{YellowOrange} E & \colorbox{YellowOrange} E \\ \hline \end{array} $$
|
|
Example 3: $$ \Huge \begin{array}{|c|c|c|c|} \hline A & B & C & E \\ \hline S & F & C & S \\ \hline A & D & E & E \\ \hline \end{array}
$$
|
|
Follow up
Word Search 2 - Return All Words
Solution
Method 1 - Backtracking
This problem can be solve by using a typical DFS method and backtracking.
We need to make sure that we don’t visit the same character again, if it is already used in word search. We can either use hashSet or we can modify the board temporarily. We will use some char like #
OR *
whenever we use some char in board, and revert after checking and backtrack.
Video explanation
Here is the video explaining this method in detail. Please check it out:
Code
|
|
|
|
Complexity
- ⏰ Time complexity:
O(m * n * 4^L)
, whereL
is the length of the word, andm x n
are the grid dimensions. As we are finding the word of lengthL
, the depth of the recursion isL
. Each cell can produce up to 4 recursive calls (for adjacent directions), leading to4^L
calls per word. This process is repeated for every cell in the worst case, which adds the factor ofm * n
. - 🧺 Space complexity:
O(L)
, due to the recursion stack used in backtracking. The depth of recursion corresponds to the length of the word.