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.
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 wordSpace: 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