Python readable solution, DFS + Stack


  • 0
    W

    Since direct DFS would cause maximum depth error, I optimized the answer with stack.
    Enlighted by https://discuss.leetcode.com/topic/17224/a-really-simple-and-readable-c-solution-only-cost-12ms

    class Solution(object):
        def solve(self, board):
            """
            :type board: List[List[str]]
            :rtype: void Do not return anything, modify board in-place instead.
            """
            if not board or not board[0]:
                return
            for i in range(len(board)):
                if board[i][0] == "O":
                    self.dfs(board, [(i,0)])
                if board[i][-1] == "O":
                    self.dfs(board, [(i, len(board[0])-1)])
            for j in range(len(board[0])):
                if board[0][j] == "O":
                    self.dfs(board, [(0, j)])
                if board[-1][j] == "O":
                    self.dfs(board, [(len(board) - 1, j)])
            
            for i in range(len(board)):
                for j in range(len(board[0])):
                    if board[i][j] == 'O':
                        board[i][j] = 'X'
                    elif board[i][j] == 'I':
                        board[i][j] = 'O'
    
                        
        def dfs(self, board, stack):
            round = [(1, 0), (-1, 0), (0, 1), (0, -1)]
            while stack:
                i,j = stack.pop()
                board[i][j] = 'I'
                for (x, y) in round:
                    nI, nJ = i + x, j + y
                    if 0 <= nI < len(board) and 0 <= nJ < len(board[0]) and board[nI][nJ] == 'O':
                        stack += [(nI, nJ)]
                
    

Log in to reply
 

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