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)$