| comments | difficulty | edit_url |
|---|---|---|
true |
Medium |
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.
For each cell, if it is X, we can add O, we can subtract
Specifically, we use a one-dimensional array X or O. After each update, we check whether the absolute value of the corresponding element equals
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
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"
}
}