A little trick to beat 100% python solution


  • 2
    A

    mark all the edges to 'S' before do the DFS, the total time will be reduced to 110ms. :)

    def solve(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        if not board:
            return
        row,col=len(board),len(board[0])
        def dfs(i,j):
            if i>0 and board[i-1][j]=='O' :
                board[i-1][j]='S'
                dfs(i-1,j)
            if j>0 and board[i][j-1]=='O' :
                board[i][j-1]='S'
                dfs(i,j-1)
            if i<row-1 and board[i+1][j]=='O' :
                board[i+1][j]='S'
                dfs(i+1,j)
            if j<col-1 and board[i][j+1]=='O' :
                board[i][j+1]='S'
                dfs(i,j+1)
            return
    
        for i in range(row):
            if board[i][0]=='O' :
                board[i][0]='S'
            if board[i][col-1]=='O':
                board[i][col-1]='S'
        for j in range(col):
            if board[0][j]=='O' :
                board[0][j]='S'
            if board[row-1][j]=='O' :
                board[row-1][j]='S'
        for i in range(row):
            if board[i][0]=='S':
                dfs(i,0)
            if board[i][col-1]=='S':
                dfs(i,col-1)
        for j in range(col):
            if board[0][j]=='S':
                dfs(0,j)
            if board[row-1][j]=='S':
                dfs(row-1,j)
        for i in range(row):
            for j in range(col):
                if board[i][j]=='S' :
                    board[i][j]='O'
                else:
                    board[i][j]='X'

  • 0
    P

    This idea is AWESOME!!!!! Thanks for sharing it!!!

    I rewrote it to make it more pythonic and achieved best run time 100ms.

    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:
                return
            m, n = len(board), len(board[0])
            
            for i, row in enumerate(board):
                index = xrange(n) if i == 0 or i == m - 1 else [0, n - 1]
                for j in index:
                    if row[j] == 'O':
                        row[j] = 'S'
            
            for i, row in enumerate(board):
                index = xrange(n) if i == 0 or i == m - 1 else [0, n - 1]
                for j in index:
                    if row[j] == 'S':
                        self.dfs(i, j, m, n, board)
            
            for row in board:
                for j in xrange(n):
                    row[j] = 'O' if row[j] == 'S' else 'X'
            return
        
        def dfs(self, i, j, m, n, board):
            if i > 0 and board[i - 1][j] == 'O':
                board[i - 1][j] = 'S'
                self.dfs(i - 1, j, m, n, board)
            if i < m - 1 and board[i + 1][j] == 'O':
                board[i + 1][j] = 'S'
                self.dfs(i + 1, j, m, n, board)
            if j > 0 and board[i][j - 1] == 'O':
                board[i][j - 1] = 'S'
                self.dfs(i, j - 1, m, n, board)
            if j < n - 1 and board[i][j + 1] == 'O':
                board[i][j + 1] = 'S'
                self.dfs(i, j + 1, m, n, board)

Log in to reply
 

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