BackTracking : WordSearch :4April POTD

Day 9/75:

Question: Word Search -(Medium)

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.

Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]        

Approach:

Approach:

Iterating through the Grid: We iterate through each cell in the grid using two nested loops.

1. For each cell (i, j), we check if the character at that cell matches the first character of the word.
2. If it does, we call the find function starting from that cell to search for the entire word.
3. If the find function returns true for any cell, indicating that the word is found starting from that cell, we return true.
4. If none of the cells match the first character of the word or if the word is not found, we return false after iterating through the entire grid.

Backtracking with DFS: We define a recursive function find to perform DFS from a specific cell (i, j) in the grid. In each recursive call, we perform the following steps:

Check if the current index idx equals the length of the word. If it does, it means we have found the entire word, so we return true.

Check if the current cell (i, j) is out of bounds or has been visited before. If it is, or if the character in the current cell does not match the character at index idx in the word, we return false.

If the character in the current cell matches the character at index idx, we mark the cell as visited (to avoid revisiting) and recursively explore its neighboring cells.

If any of the recursive calls return true, indicating that the word is found starting from the current cell, we propagate the true value back up the call stack.

If none of the recursive calls return true, we backtrack by marking the current cell as unvisited and continue exploring other paths.

Code:

Complexity Analysis:

• Time complexity of the solution depends on the dimensions of the grid (m x n) and the length of the word (l). In the worst case, where every cell is explored and all possible paths are traversed, the time complexity is O(m * n * 4^l), where 4^l represents the number of recursive calls at each step of DFS.
• Space complexity is O(l) for the recursion stack, where l is the length of the word. Additionally, the space complexity of the input grid is O(m * n) for storing the characters.

Related Question:

WORD SEARCH II : https://leetcode.com/problems/word-search-ii/description/