Share my python solution - iterative DFS, 120ms


  • 0
    D

    The idea is to push all 'O's along the border onto stack and do DFS

    class Solution(object):
        def solve(self, board):
            """
            :type board: List[List[str]]
            :rtype: void Do not return anything, modify board in-place instead.
            """
            def _checkin(row, col):
                # change 'O' to 'Y' and push location to stack
                board[row][col] = 'Y'
                stack.append((row, col))
    
            num_rows = len(board)
            if num_rows > 2:
                num_cols = len(board[0])
                if num_cols > 2:
                    stack = []
                    # checkin all 'O's along the border
                    for i in xrange(num_rows):
                        if board[i][0] == 'O':
                            _checkin(i, 0)
                        if board[i][num_cols - 1] == 'O':
                            _checkin(i, num_cols - 1)
                    for j in xrange(1, num_cols - 1):
                        if board[0][j] == 'O':
                            _checkin(0, j)
                        if board[num_rows - 1][j] == 'O':
                            _checkin(num_rows - 1, j)
    
                    while stack:
                        i, j = stack.pop()
                        # checkin four adjecent cells to they are not checked in
                        i -= 1
                        if i >= 0 and board[i][j] == 'O':
                            _checkin(i, j)
                        i += 2
                        if i < num_rows and board[i][j] == 'O':
                            _checkin(i, j)
                        i -= 1
                        j -= 1
                        if j >= 0 and board[i][j] == 'O':
                            _checkin(i, j)
                        j += 2
                        if j < num_cols and board[i][j] == 'O':
                            _checkin(i, j)
    
                    # change 'O' to 'X' and 'Y' back to 'O'
                    for i in xrange(num_rows):
                        for j in xrange(num_cols):
                            if board[i][j] == 'O':
                                board[i][j] = 'X'
                            elif board[i][j] == 'Y':
                                board[i][j] = 'O'

Log in to reply
 

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