AC Python DFS Solution


  • 0
    L
    class Solution(object):
        def exist(self, board, word):
            """
            :type board: List[List[str]]
            :type word: str
            :rtype: bool
            """
            row = len(board)
            col = len(board[0])
            visited = [[False] * col for i in range(row)]
            for i in range(row):
                for j in range(col):
                    if board[i][j] == word[0]:
                        result = self.dfs(board, visited, i, j, row, col, word[1:])
                        if result:
                            return True
            return False
        
        def dfs(self, board, visited, i, j, row, col, word):
            if word == '':
                return True
            visited[i][j] = True
            for m, n in [(i, j + 1), (i, j - 1), (i - 1, j), (i + 1, j)]:
                if 0 <= m and m <= row - 1 and 0 <= n and n <= col - 1 and board[m][n] == word[0] and not visited[m][n]:
                    if self.dfs(board, visited, m, n, row, col, word[1:]):
                        return True
            visited[i][j] = False
            return False
    

Log in to reply
 

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