Problme Link
Problem Statement:
You are given a R x C
grid of lowercase characters and a string s
. The task is to check if the string s
can be found in the grid by sequentially connecting adjacent cells. A cell is considered adjacent if it is horizontally or vertically neighboring. The same cell may not be used more than once in the construction of the string.
Approach:
To solve this problem, we can use DepthFirst Search (DFS). The idea is to start from each cell in the grid and try to construct the string s
by exploring adjacent cells in the grid. We recursively explore all possible paths in the grid that can form the string. If we find such a path, the function returns true
. Otherwise, after exploring all possibilities, the function returns false
.
Detailed Explanation:

DFS Traversal:
 We define a DFS function that takes the current position in the grid
(i, j)
, the current indexk
of the strings
, and the grid itself.  If
k
equals the length of the string, it means we’ve successfully found the string in the grid, so we returntrue
.  If the current position
(i, j)
is out of bounds or the character atboard[i][j]
does not matchs[k]
, returnfalse
.
 We define a DFS function that takes the current position in the grid

Marking Cells as Visited:
 To avoid using the same cell more than once, we temporarily mark the current cell as visited by replacing its value with a special marker (e.g.,
#
).  After exploring all possible paths from the current cell, restore its original value.
 To avoid using the same cell more than once, we temporarily mark the current cell as visited by replacing its value with a special marker (e.g.,

Exploring All Directions:
 From the current cell, we recursively explore the four possible directions (up, down, left, right) to see if we can continue forming the string.

Initial Search:
 The search begins from each cell in the grid. If we find a path that successfully forms the string, we return
true
. If after checking all cells the string is not found, we returnfalse
.
 The search begins from each cell in the grid. If we find a path that successfully forms the string, we return
Example:
Consider the grid:
A B C E
S F C S
A D E E
and the word ABCCED
.
Starting from A
at (0, 0)
:
 Move right to
B
, then toC
, then right again toC
, then down toE
, and finally down toD
. The wordABCCED
is found.
Complexity:

Time Complexity: The time complexity is
O(R * C * 4^L)
, whereR
andC
are the dimensions of the grid, andL
is the length of the word. In the worst case, we explore up to four directions for each character in the word, but the actual complexity is often much lower due to early termination. 
Space Complexity: The space complexity is
O(L)
due to the recursive call stack, whereL
is the length of the word.