16.04. Tic-Tac-Toe

Description

Design an algorithm to figure out if someone has won a game of tic-tac-toe. Input is a string array of size N x N, including characters " ", "X" and "O", where " " represents a empty grid.

The rules of tic-tac-toe are as follows:

Players place characters into an empty grid(" ") in turn.
The first player always place character "O", and the second one place "X".
Players are only allowed to place characters in empty grid. Replacing a character is not allowed.
If there is any row, column or diagonal filled with N same characters, the game ends. The player who place the last charater wins.
When there is no empty grid, the game ends.
If the game ends, players cannot place any character further.

If there is any winner, return the character that the winner used. If there's a draw, return "Draw". If the game doesn't end and there is no winner, return "Pending".

Example 1:

Input:  board = ["O X"," XO","X O"]

Output:  "X"

Example 2:

Input:  board = ["OOX","XXO","OXO"]

Output:  "Draw"

Explanation:  no player wins and no empty grid left

Example 3:

Input:  board = ["OOX","XXO","OX "]

Output:  "Pending"

Explanation:  no player wins but there is still a empty grid

Note:

1 <= board.length == board[i].length <= 100
Input follows the rules.

Solutions

Solution 1: Counting

Thinking

Decide a win, a draw, or an unfinished board. Recounting every line after the fact is correct but redundant.

Score X as \(+1\) and O as \(-1\); an absolute sum of \(n\) on a row, column, or diagonal is a full line.

Accumulate \(rows\), \(cols\), \(dg\), and \(udg\) while scanning; return the cell’s character when some absolute value hits \(n\). No spaces means a draw, otherwise Pending.

For each cell, if it is X, we can add \(1\) to the count; if it is O, we can subtract \(1\) from the count. When the absolute value of the count of a row, column, or diagonal equals \(n\), it means that the current player has placed \(n\) identical characters in that row, column, or diagonal, and the game is over. We can return the corresponding character.

Specifically, we use a one-dimensional array \(rows\) and \(cols\) of length \(n\) to represent the count of each row and column, and use \(dg\) and \(udg\) to represent the count of the two diagonals. When a player places a character at \((i, j)\), we update the corresponding elements in the arrays \(rows\), \(cols\), \(dg\), and \(udg\) based on whether the character is X or O. After each update, we check whether the absolute value of the corresponding element equals \(n\). If it does, it means that the current player has placed \(n\) identical characters in that row, column, or diagonal, and the game is over. We can return the corresponding character.

Finally, we traverse the entire board. If there is a character , it means that the game is not over yet, and we return Pending. Otherwise, we return Draw.

The time complexity is \(O(n^2)\), and the space complexity is \(O(n)\), where \(n\) is the side length of the board.

Python3JavaC++GoTypeScriptSwift

class Solution:
    def tictactoe(self, board: List[str]) -> str:
        n = len(board)
        rows = [0] * n
        cols = [0] * n
        dg = udg = 0
        has_empty_grid = False
        for i, row in enumerate(board):
            for j, c in enumerate(row):
                v = 1 if c == 'X' else -1
                if c == ' ':
                    has_empty_grid = True
                    v = 0
                rows[i] += v
                cols[j] += v
                if i == j:
                    dg += v
                if i + j + 1 == n:
                    udg += v
                if (
                    abs(rows[i]) == n
                    or abs(cols[j]) == n
                    or abs(dg) == n
                    or abs(udg) == n
                ):
                    return c
        return 'Pending' if has_empty_grid else 'Draw'

class Solution {
    public String tictactoe(String[] board) {
        int n = board.length;
        int[] rows = new int[n];
        int[] cols = new int[n];
        int dg = 0, udg = 0;
        boolean hasEmptyGrid = false;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                char c = board[i].charAt(j);
                if (c == ' ') {
                    hasEmptyGrid = true;
                    continue;
                }
                int v = c == 'X' ? 1 : -1;
                rows[i] += v;
                cols[j] += v;
                if (i == j) {
                    dg += v;
                }
                if (i + j + 1 == n) {
                    udg += v;
                }
                if (Math.abs(rows[i]) == n || Math.abs(cols[j]) == n || Math.abs(dg) == n
                    || Math.abs(udg) == n) {
                    return String.valueOf(c);
                }
            }
        }
        return hasEmptyGrid ? "Pending" : "Draw";
    }
}

class Solution {
public:
    string tictactoe(vector<string>& board) {
        int n = board.size();
        vector<int> rows(n), cols(n);
        int dg = 0, udg = 0;
        bool hasEmptyGrid = false;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                char c = board[i][j];
                if (c == ' ') {
                    hasEmptyGrid = true;
                    continue;
                }
                int v = c == 'X' ? 1 : -1;
                rows[i] += v;
                cols[j] += v;
                if (i == j) {
                    dg += v;
                }
                if (i + j + 1 == n) {
                    udg += v;
                }
                if (abs(rows[i]) == n || abs(cols[j]) == n || abs(dg) == n || abs(udg) == n) {
                    return string(1, c);
                }
            }
        }
        return hasEmptyGrid ? "Pending" : "Draw";
    }
};

func tictactoe(board []string) string {
    n := len(board)
    rows := make([]int, n)
    cols := make([]int, n)
    dg, udg := 0, 0
    hasEmptyGrid := false
    for i, row := range board {
        for j, c := range row {
            if c == ' ' {
                hasEmptyGrid = true
                continue
            }
            v := 1
            if c == 'O' {
                v = -1
            }
            rows[i] += v
            cols[j] += v
            if i == j {
                dg += v
            }
            if i+j == n-1 {
                udg += v
            }
            if abs(rows[i]) == n || abs(cols[j]) == n || abs(dg) == n || abs(udg) == n {
                return string(c)
            }
        }
    }
    if hasEmptyGrid {
        return "Pending"
    }
    return "Draw"
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

function tictactoe(board: string[]): string {
    const n = board.length;
    const rows = Array(n).fill(0);
    const cols = Array(n).fill(0);
    let [dg, udg] = [0, 0];
    let hasEmptyGrid = false;
    for (let i = 0; i < n; ++i) {
        for (let j = 0; j < n; ++j) {
            const c = board[i][j];
            if (c === ' ') {
                hasEmptyGrid = true;
                continue;
            }
            const v = c === 'X' ? 1 : -1;
            rows[i] += v;
            cols[j] += v;
            if (i === j) {
                dg += v;
            }
            if (i + j === n - 1) {
                udg += v;
            }
            if (
                Math.abs(rows[i]) === n ||
                Math.abs(cols[j]) === n ||
                Math.abs(dg) === n ||
                Math.abs(udg) === n
            ) {
                return c;
            }
        }
    }
    return hasEmptyGrid ? 'Pending' : 'Draw';
}

class Solution {
    func tictactoe(_ board: [String]) -> String {
        let n = board.count
        var rows = Array(repeating: 0, count: n)
        var cols = Array(repeating: 0, count: n)
        var diagonal = 0, antiDiagonal = 0
        var hasEmptyGrid = false

        for i in 0..<n {
            for j in 0..<n {
                let c = Array(board[i])[j]
                if c == " " {
                    hasEmptyGrid = true
                    continue
                }
                let value = c == "X" ? 1 : -1
                rows[i] += value
                cols[j] += value
                if i == j {
                    diagonal += value
                }
                if i + j == n - 1 {
                    antiDiagonal += value
                }
                if abs(rows[i]) == n || abs(cols[j]) == n || abs(diagonal) == n || abs(antiDiagonal) == n {
                    return String(c)
                }
            }
        }

        return hasEmptyGrid ? "Pending" : "Draw"
    }
}

16.04. Tic-Tac-Toe

Description

Solutions

Solution 1: Counting

Comments