Leetcode 794 - Valid Tic-Tac-Toe State

Note:

  • Don’t use DFS coz X or O is not to be placed along some path. It can be just random.
  • Find out the pattern!
  • If Both X and O win, it’s false.
  • If there are more Os than Xs, it’s false.
  • If X wins but there are same number of Xs and Os, it’s false.
  • Likewise, if O wins but there are more Xs than Os, it’s false.

Question:

Given a Tic-Tac-Toe board as a string array board, return true if and only if it is possible to reach this board position during the course of a valid tic-tac-toe game.

The board is a 3 x 3 array that consists of characters ' ', 'X', and 'O'. The ‘ ‘ character represents an empty square.

Here are the rules of Tic-Tac-Toe:

  • Players take turns placing characters into empty squares ‘ ‘.
  • The first player always places ‘X’ characters, while the second player always places ‘O’ characters.
  • ‘X’ and ‘O’ characters are always placed into empty squares, never filled ones.
  • The game ends when there are three of the same (non-empty) character filling any row, column, or diagonal.
  • The game also ends if all squares are non-empty.
  • No more moves can be played if the game is over.

Example:

img

1
2
3
Input: board = ["O  ","   ","   "]
Output: false
Explanation: The first player always plays "X".

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
* @param {string[]} board
* @return {boolean}
*/
var validTicTacToe = function(board) {
let xCount = 0, oCount = 0;
let xPos = [], oPos = [];
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
if (board[i][j] === 'X') {
xCount++;
xPos.push([i, j]);
}
if (board[i][j] === 'O') {
oCount++;
oPos.push([i, j]);
}
}
}
if (oCount - xCount >= 1) return false;
if (Math.abs(xCount - oCount) > 1) return false;
let isXWin = false, isOWin = false;
ifBothWins(board);
const isBothWin = isXWin && isOWin;
if (isBothWin) return false;
if (isXWin && xCount === oCount) return false;
if (isOWin && xCount !== oCount) return false;
return true;

function ifBothWins(grid) {
for (let i = 0; i < 3; i++) {
if (grid[i] === 'XXX' || (grid[0][i] + grid[1][i] + grid[2][i] === 'XXX')) isXWin = true;;
if (grid[i] === 'OOO' || (grid[0][i] + grid[1][i] + grid[2][i] === 'OOO')) isOWin = true;
}
if (grid[0][0] + grid[1][1] + grid[2][2] === 'XXX' || grid[0][2] + grid[1][1] + grid[2][0] === 'XXX') isXWin = true;
if (grid[0][0] + grid[1][1] + grid[2][2] === 'OOO' || grid[0][2] + grid[1][1] + grid[2][0] === 'OOO') isOWin = true;
}
};