Python standard backtracking


  • 0
    W

    Idea is to do DFS on every position of the board, return True as soon as their is a valid path.

    Use visited as a set to store the positions that have been visited, preventing going back to visited positions. Need to undo the visited at the end.

    def exist(self, board, word):
        for i in range(len(board)):
            for j in range(len(board[0])):
                if self.dfs(board, word, i, j, 0, set()):
                    return True
        return False
    
    def dfs(self, board, word, i, j, index, visited):
        if index >= len(word): return True
        if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or (i, j) in visited or board[i][j] != word[index]: return False
        visited.add((i, j))
        ret = self.dfs(board, word, i+1, j, index+1, visited) or self.dfs(board, word, i-1, j, index+1, visited) or self.dfs(board, word, i, j-1, index+1, visited) or self.dfs(board, word, i, j+1, index+1, visited)
        visited.remove((i, j))
        return ret

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.