Reference: LeetCode
Difficulty: Medium

Problem

A Tic-Tac-Toe board is given 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, and 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 3 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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// "X" goes first, then "O" goes next!

// "O "
// " "
// " " --> false

// "XOX"
// " X "
// " " --> false

// "XXX"
// " X "
// " " --> false

// "XOX"
// "O O"
// "XOX" --> true

Analysis

Naive

Necessary conditions for a tic-tac-toe board to be valid:

  • Since players take turns and X goes first. The number of X‘s must be equal to or one greater than the number of O.
  • A player that wins has to win on the move that they take:
    • If X wins, the number of X is one more than the number of O.
    • If O wins, the number of X is equal to the number of O.
  • The board can’t simultaneously have three Xs and three Os in a row, since once one player has won (on their move), there are no subsequent moves.

We check these conditions in reverse. In any board, one player, or both players have won.

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
public boolean validTicTacToe(String[] board) {
// assume board is non-empty
// count
int xCount = 0, oCount = 0;
for (String row : board) {
for (char ch : row.toCharArray()) {
if (ch == 'X') xCount++;
if (ch == 'O') oCount++;
}
}

// count condition
if (xCount != oCount && xCount != oCount + 1) return false;
// THEN: xCount == oCount OR xCount == oCount + 1

// LeetCode Solution:
// if (win(board, 'X') && xCount != oCount + 1) return false;
// if (win(board, 'O') && xCount != oCount) return false;

// My Solution (list all situations):
boolean xWin = win(board, 'X');
boolean oWin = win(board, 'O');

// both win
if (xWin && oWin) {
return false;
}
// one player wins
else if (xWin || oWin) {
if (xWin && xCount == oCount + 1) return true;
else if (oWin && xCount == oCount) return true;
else return false;
}
// no one wins
else {
return true;
}
}

// check if player wins in board
private boolean win(String[] B, char player) {
for (int i = 0; i < 3; ++i) {
// for each row
if (player == B[i].charAt(0) && player == B[i].charAt(1) && player == B[i].charAt(2)) {
return true;
}
// for each column
if (player == B[0].charAt(i) && player == B[1].charAt(i) && player == B[2].charAt(i)) {
return true;
}
}

// two diagonals
if (player == B[0].charAt(0) && player == B[1].charAt(1) && player == B[2].charAt(2)) {
return true;
}
if (player == B[0].charAt(2) && player == B[1].charAt(1) && player == B[2].charAt(0)) {
return true;
}

return false;
}

Time: $O(1)$
Space: $O(1)$


Comment