[LeetCode] Problem 794 - Valid Tic-Tac-Toe State

Posted on | In ,

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

No.1

Input: board = [“O “, “ “, “ “]

Output: false

Explanation: The first player always plays “X”.

No.2

Input: board = [“XOX”, “ X “, “ “]

Output: false

Explanation: Players take turns making moves.

No.3

Input: board = [“XXX”, “ “, “OOO”]

Output: false

No.4

Input: board = [“XOX”, “O O”, “XOX”]

Output: true

Note

  • board is a length-3 array of strings, where each string board[i] has length 3.
  • Each board[i][j] is a character in the set {“ “, “X”, “O”}.

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
// X X X
// O O _
// O _ _
public boolean validTicTacToe(String[] board) {
    int[] xRes = getWin(board, 'X');
    int[] oRes = getWin(board, 'O');
    int xCount = xRes[0];
    int xWin = xRes[1];
    int oCount = oRes[0];
    int oWin = oRes[1];

    if (xCount != oCount && xCount != oCount + 1)
        return false;

    if (xWin > 1 && oWin > 1)
        return false;

    if ((xWin == 1 && xCount == oCount) || (oWin == 1 && xCount == oCount + 1))
        return false;

    return true;
}

private int[] getWin(String[] board, char ch) {
    int count = 0;
    int win = 0;
    char[][] col = new char[3][3];
    char[] diag1 = new char[3];
    char[] diag2 = new char[3];
    char[] pattern = new char[] {ch, ch, ch};

    for (int i = 0; i < 3; i++) {
        diag1[i] = board[i].charAt(i);
        diag2[i] = board[i].charAt(2 - i);

        for (int j = 0; j < 3; j++) {
            if (board[i].charAt(j) == ch)
                count++;

            col[j][i] = board[i].charAt(j);
        }
    }

    win += Arrays.equals(diag1, pattern) ? 1 : 0;
    win += Arrays.equals(diag2, pattern) ? 1 : 0;

    for (int i = 0; i < 3; i++) {
        win += Arrays.equals(board[i].toCharArray(), pattern) ? 1 : 0;
        win += Arrays.equals(col[i], pattern) ? 1 : 0;
    }

    return new int[] {count, win};
}