Python solution with detailed explanation


  • 0
    G

    Solution

    Design Tic-Tac-Toe https://leetcode.com/problems/design-tic-tac-toe/

    Brute Force Solution

    • There are four strikes that can win for you. Row, Col, Diagonal, Anti-Diagonal.
    • Diagonal: row == col. Anti-Diagonal: row+col=self.n-1. Use this condition to check diagonal and anti-diagonal.
    • O(N) solution: At every move, test each strike if they have the same player. This will be like 4 times N.
    class TicTacToe(object):
        def __init__(self, n):
            """
            Initialize your data structure here.
            :type n: int
            """
            self.board = [[-1]*n for _ in range(n)]
            self.n = n
    
        def move(self, row, col, player):
            """
            Player {player} makes a move at ({row}, {col}).
            @param row The row of the board.
            @param col The column of the board.
            @param player The player, can be either 1 or 2.
            @return The current winning condition, can be either:
                    0: No one wins.
                    1: Player 1 wins.
                    2: Player 2 wins.
            :type row: int
            :type col: int
            :type player: int
            :rtype: int
            """
            self.board[row][col] = player
            col_check = row_check = diagonal_check = anti_diagonal_check = True
            
            for j in range(self.n):
                if self.board[row][j] != player:
                    col_check = False
                    break
            if col_check:
                return player
                
            for i in range(self.n):
                if self.board[i][col] != player:
                    row_check = False
                    break
            if row_check:
                return player
                
            if row == col:
                for k in range(self.n):
                    if self.board[k][k] != player:
                        diagonal_check = False
                        break                
                if diagonal_check:
                    return player
                    
            if row + col == self.n-1:
                r,c = 0, self.n-1
                for k in range(self.n):
                    if self.board[r][c] != player:
                        anti_diagonal_check = False
                        break
                    r,c = r+1,c-1
                if anti_diagonal_check:
                    return player
                    
            return 0
    

    Optimized Solution

    • O(1) solution: Keep 2 arrays nrow and ncol. Keep 2 variables diagonal and anti_diagonal.
    • nrow[i] = [player_index, count] and similarly ncol[i] = [player_index, count]. At each move, there is a win with respect to row if the current player is row[i,0] and its previous count is N-1. Similarly, we can derive a condition for col win.
    • if row == col, then we test the diagonal variable whether it stored the current player and whether its previous count was N-1.
    • if row+col =N-1, then we check the anti-diagonal.
    class TicTacToe(object):
        def __init__(self, n):
            """
            Initialize your data structure here.
            :type n: int
            """
            self.row, self.col = [None]*n, [None]*n
            self.diagonal, self.anti_diagonal = None, None
            self.n = n
            
    
        def move(self, row, col, player):
            """
            Player {player} makes a move at ({row}, {col}).
            @param row The row of the board.
            @param col The column of the board.
            @param player The player, can be either 1 or 2.
            @return The current winning condition, can be either:
                    0: No one wins.
                    1: Player 1 wins.
                    2: Player 2 wins.
            :type row: int
            :type col: int
            :type player: int
            :rtype: int
            """
            diagonal_check = anti_diagnoal = True
            if self.row[row] == None:
                self.row[row] = [player, 1]
            elif self.row[row][0] == player:
                if self.row[row][1] == self.n-1:
                    return player
                else:
                    self.row[row][1] = self.row[row][1] + 1
                
            if self.col[col] == None:
                self.col[col] = [player, 1]
            elif self.col[col][0] == player:
                if self.col[col][1] == self.n-1:
                    return player
                else:
                    self.col[col][1] = self.col[col][1] + 1            
                
            if row == col:
                if self.diagonal == None:
                    self.diagonal = [player, 1]
                elif self.diagonal[0] == player:
                    if self.diagonal[1] == self.n-1:
                        return player
                    else:
                        self.diagonal[1] = self.diagonal[1] + 1
    
            if row + col == self.n-1:
                if self.anti_diagonal == None:
                    self.anti_diagonal = [player, 1]
                elif self.anti_diagonal[0] == player:
                    if self.anti_diagonal[1] == self.n-1:
                        return player
                    else:
                        self.anti_diagonal[1] = self.anti_diagonal[1] + 1            
            return 0
    

    Also check this brilliant solution: https://discuss.leetcode.com/topic/44548/java-o-1-solution-easy-to-understand/2


Log in to reply
 

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