Leetcode Word Search

Question

I am currently trying to solve the Word Search problem on leetcode. The question is as follows:

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

My attempt is as follows:

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def backtrack(loc: tuple, i: int) -> bool:
            x = loc[0]
            y = loc[1]
            if loc in seen:
                return False
            if  x >= len(board) or y >= len(board[0]):
                return False
            if 0 > x or 0 > y:
                return False
            if board[x][y] != word[i]:
                return False
            if i >= len(word)- 1:
                return True
            seen.add(loc)
            return backtrack((x+1, y), i+1) or backtrack((x-1, y), i+1) or backtrack((x, y-1), i+1) or backtrack((x,y+1), i+1)
        for i in range(len(board)):
            for j in range(len(board[i])):
                if board[i][j] == word[0]:
                    seen = set()
                    if backtrack((i, j), 0):
                        return True
        return False

Now I am able to solve the problem if I was to edit the board input to check if a state was visited but I would prefer not to modify the input array so I chose to use a hash set to do it. However I'm unable to properly implement the check and that is why my code is failing so I was hoping that someone could help me out. Thank you!

Answer 1

For backtracking algorithms, you have to take back the "move" you've made. So in this case, you have to remove the loc from seen after you make the recursive calls. Here is a proposed simple fix:

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def backtrack(loc: tuple, i: int) -> bool:
            x = loc[0]
            y = loc[1]
            if loc in seen:
                return False
            if  x >= len(board) or y >= len(board[0]):
                return False
            if 0 > x or 0 > y:
                return False
            if board[x][y] != word[i]:
                return False
            if i >= len(word)- 1:
                return True
            seen.add(loc)
            res = backtrack((x+1, y), i+1) or backtrack((x-1, y), i+1) or backtrack((x, y-1), i+1) or backtrack((x,y+1), i+1)
            seen.remove(loc)  # Removes loc from seen
            return res
        for i in range(len(board)):
            for j in range(len(board[i])):
                if board[i][j] == word[0]:
                    seen = set()
                    if backtrack((i, j), 0):
                        return True
        return False