Help request! why my python solution 1 timeout but solution 2 very fast


  • 0
    R

    Solution 1

    from collections import deque
    
    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
            
            for row in xrange(len(board)):
                if board[row][0] == 'O':
                    self.findClose(row, 0, board)
                
                if board[row][len(board[0])-1] == 'O':
                    self.findClose(row, len(board[0])-1, board)
            
            for col in xrange(len(board[0])):
                if board[0][col] == 'O':
                    self.findClose(0, col, board)
                
                if board[len(board)-1][col] == 'O':
                    self.findClose(len(board)-1, col, board)
            
            for r in xrange(len(board)):
                for c in range(len(board[0])):
                    if  board[r][c] == 'O':
                        board[r][c]='X'
                    elif board[r][c] == '*':
                        board[r][c] = 'O'
                        
        def findClose(self, r, c, board):
    
            directs = [(0,1), (0, -1), (1, 0), (-1, 0)]
            q=deque()
            q.append((r,c))
            while q:
                currentX, currentY = q.popleft()
                board[currentX][currentY] = '*'
                for d in directs:
                    x = currentX+d[0]
                    y = currentY+d[1]
                    
                    if 0<=x<len(board) and 0<=y<len(board[0]) and board[x][y] == 'O':
                        q.append((x, y))  
    

    Solution 2

    
    from collections import deque
    
    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
            
            for row in xrange(len(board)):
                if board[row][0] == 'O':
                    self.findClose(row, 0, board)
                
                if board[row][len(board[0])-1] == 'O':
                    self.findClose(row, len(board[0])-1, board)
            
            for col in xrange(len(board[0])):
                if board[0][col] == 'O':
                    self.findClose(0, col, board)
                
                if board[len(board)-1][col] == 'O':
                    self.findClose(len(board)-1, col, board)
            
            for r in xrange(len(board)):
                for c in range(len(board[0])):
                    if  board[r][c] == 'O':
                        board[r][c]='X'
                    elif board[r][c] == '*':
                        board[r][c] = 'O'
                        
        def findClose(self, r, c, board):
    
            directs = [(0,1), (0, -1), (1, 0), (-1, 0)]
            q=deque()
            q.append((r,c))
            board[r][c]='*'
            while q:
                currentX, currentY = q.popleft()
                for d in directs:
                    x = currentX+d[0]
                    y = currentY+d[1]
                    
                    if 0<=x<len(board) and 0<=y<len(board[0]) and board[x][y] == 'O':
                        q.append((x, y))
                        board[x][y]='*'
            
        
                    
                    
                    
    

Log in to reply
 

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