# 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

## 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

##### Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.

### 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

This site uses Akismet to reduce spam. Learn how your comment data is processed.