Share my python solution - iterative DFS, 120ms

• 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'``````

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