LeetCode 348: Design Tic-Tac-Toe

link

For each player we can keep four counts: (1) per row (2) per col (3) the major diagonal (4) the minor diagonal. After the move, if any of these four counts is n, the player won.

OperationTimeSpace
__init__\mathcal{O}(n)\mathcal{O}(n)
move\mathcal{O}(1)\mathcal{O}(1)
class TicTacToe:

    def __init__(self, n: int):
        self.n = n
        self.row_count = [[0, 0] for _ in range(n)]
        self.col_count = [[0, 0] for _ in range(n)]
        self.major_count = [0, 0]
        self.minor_count = [0, 0]

    def is_winner(self, row, col, player):
        if self.row_count[row][player - 1] == self.n:
            return True

        if self.col_count[col][player - 1] == self.n:
            return True

        if self.major_count[player - 1] == self.n:
            return True

        if self.minor_count[player - 1] == self.n:
            return True

        return False

    def move(self, row: int, col: int, player: int) -> int:
        def is_major_diag(row, col):
            return row == col

        def is_minor_diag(row, col):
            return row+col == (self.n-1)

        self.row_count[row][player - 1] += 1
        self.col_count[col][player - 1] += 1
        self.major_count[player - 1] += 1 if is_major_diag(row, col) else 0
        self.minor_count[player - 1] += 1 if is_minor_diag(row, col) else 0

        return player if self.is_winner(row, col, player) else 0


# Your TicTacToe object will be instantiated and called as such:
# obj = TicTacToe(n)
# param_1 = obj.move(row,col,player)

For better readability we could encapsulate counts in a Player class.

class Player:
    def __init__(self, n):
        self.n = n
        self.row_count = [0] * n
        self.col_count = [0] * n
        self.major_diag_count = 0
        self.minor_diag_count = 0
        self.last_move = None

    def move(self, row, col):
        self.row_count[row] += 1
        self.col_count[col] += 1
        self.major_diag_count += 1 if row == col else 0
        self.minor_diag_count += 1 if (row + col) == (self.n - 1) else 0
        self.last_move = (row, col)

    def is_full_row(self):
        return self.row_count[self.last_move[0]] == self.n

    def is_full_col(self):
        return self.col_count[self.last_move[1]] == self.n

    def is_full_diag(self):
        return self.major_diag_count == self.n or self.minor_diag_count == self.n


class TicTacToe:

    def __init__(self, n: int):
        self.players = {1: Player(n), 2: Player(n)}

    def is_winner(self, player):
        return player.is_full_row() or player.is_full_col() or player.is_full_diag()

    def move(self, row: int, col: int, player: int) -> int:
        p = self.players[player]
        p.move(row, col)
        return player if self.is_winner(p) else 0


# Your TicTacToe object will be instantiated and called as such:
# obj = TicTacToe(n)
# param_1 = obj.move(row,col,player)

Leave a comment