BFS based, don't know how leetcode allows assignment to str since string in python is immutable.

```
class Solution(object):
def solve(self, board):
if not board: return
lenth, height, stack=len(board[0]), len(board), []
q=[[(0, height-1), [i for i in xrange(lenth)]],[[j for j in xrange(height)],(0, lenth-1)]]
while q:
ii, jj=q.pop()
for i in ii:
for j in jj:
if board[i][j]=='O': stack+=(i,j),
while stack:
i,j=stack.pop()
if 0<=i<height and 0<=j<lenth and board[i][j]=='O':
board[i][j]='#'
stack+=(i+1,j),(i,j+1),(i-1,j),(i,j-1),
for i in xrange(height):
for j in xrange(lenth):
if board[i][j]=='O': board[i][j]='X'
if board[i][j]=='#': board[i][j]='O'
```