DSAPROB8 - Editorial

editorial
, ,
1

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 Depth-First 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:

  1. DFS Traversal:

    • We define a DFS function that takes the current position in the grid (i, j), the current index k of the string s, 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 return true.
    • If the current position (i, j) is out of bounds or the character at board[i][j] does not match s[k], return false.

  2. 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.

  3. 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.

  4. 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 return false.

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 to C, then right again to C, then down to E, and finally down to D. The word ABCCED is found.

Complexity:

  • Time Complexity: The time complexity is O(R * C * 4^L), where R and C are the dimensions of the grid, and L 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, where L is the length of the word.