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 word
  • Space: O(L) for the recursion call stack height

    Leave a Reply

    Your email address will not be published. Required fields are marked *