# Word Search | InterviewBit | LeetCode | Solution Explained

79. Word Search is a medium problem on LeetCode, also on InterviewBit. I explain a solution based on the backtracking approach. We use depth first search (DFS) for this problem. Problem Link.

**Contents**hide

## Logic

- To search for the word, we must first know where to start
- We can iterate over the entire grid and then start our search from the first match *
- Once we have found a match, we can start a DFS from that point
- The dfs needs to account for the following:
- the position: (x, y)
- the current character we are looking for: indexed with (i)

- Thus,
`dfs(x, y, i)`

is our structure

## Common Issues

One issue is visiting – since we know that `dfs`

needs this extra `visited`

array, creating one is a huge pain – taking O(m*n) **extra** space. What we can do instead is set `board[x][y] = -1`

. Think about this as “burning” the path you took before, so that you can no longer take it.

All is fine till you realize: *there can be multiple “starting points” *– if the search string is “AX…” then there can be multiple “A”s in the board. This is an easy fix, right? Just start a dfs from *each* of the points!

Not so fast! We can have cases where we have **burnt** our path, so we can no longer take it. If you are confused at this point, I have explained this particular part of backtracking in detail in the video solution.

We need to do two things:

- “visit” the nodes – burn the path
- BUT ALSO preserve the path for later.

The fix to this problem is … surprisingly easy. The code down below uses the `temp`

variable that does the job for us.

## Code

class Solution: def exist(self, board: List[List[str]], word: str) -> bool: def dfs(x, y, i): if i >= l: return True if not (0 <= x < m and 0 <= y < n): return False if board[x][y] != word[i]: return False if board[x][y] == -1: return False board[x][y] = -1 temp = dfs(x+1, y, i+1) or dfs(x-1, y, i+1) or dfs(x, y+1, i+1) or dfs(x, y-1, i+1) board[x][y] = word[i] return temp l, m, n = len(word), len(board), len(board[0]) for x in range(m): for y in range(n): if board[x][y] == word[0]: if dfs(x, y, 0): return True return False

Note how the temp variable stores the result of the dfs-es that we generated in the line 11. This let’s us start a dfs *with the paths burnt out* and once we are done with that, we *restore* the path, using `board[x][y] = word[i]`

.

## Complexity Analysis

`Time: O(M*N*3^L)`

where M and N are the dimensions of the board and L is the length of the input word`Space: O(L)`

for the recursion call stack height

### Recommended Posts

##### Gas Station | InterviewBit | Solution Explained

June 13, 2022

##### Reverse integer | InterviewBit | LeetCode | Solution Explained

January 24, 2022

##### Furthest Building You Can Reach | LeetCode | Solution Explained

January 20, 2022