Amazon interview question round 3 Word Search Leetcode 79

I was asked to solve the problem called Word Search (both medium and hard version) at Amazon interview. Though I was able to solve both of them, this post is about the medium one. I used a simple backtracking algorithm with a runtime of O(m*n*3^s), where s is the length of the given word we are searching for with no extra space, excluding space required for the call stacks.

Solution:

I used a simple backtracking algorithm. This algorithm explores the grid both vertically and horizontally in all 4 directions and tries to find the word, or we reach the dead-end and backtracks one step to explore other possible paths. By marking those cells we already visited, we make sure that each letter cell is used only once.

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        
        def dfs(board, x, y, word, i):
            if len(word) == i:
                return True
            
            if not (0<=x< len(board) and 0<=y< len(board[x])):
                return False
            if board[x][y] != word[i]:
                return False
        
            ch = board[x][y]
            board[x][y] = '#'
            
            for d in (1, 0), (-1, 0), (0, 1), (0, -1):
                    if dfs(board, x + d[0], y + d[1], word, i+1):
                        return True
            
            board[x][y] = ch
            return False
        
        for i in range(len(board)):
            for j in range(len(board[i])):
                if dfs(board, i, j, word, 0):
                    return True
        
        return False