Leetcode 794. Valid Tic-Tac-Toe State

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:
Input: board = ["O  ", "   ", "   "]
Output: false
Explanation: The first player always plays "X".

Example 2:
Input: board = ["XOX", " X ", "   "]
Output: false
Explanation: Players take turns making moves.

Example 3:
Input: board = ["XXX", "   ", "OOO"]
Output: false

Example 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"}
• 
  

Analysis:

The problem only asks if the given board is valid. A board is valid only if 

1. number of X - number of O == 0

2. number of X - number of O == 1

If the number of X is equal to number of O, we need to check player X does not win. Otherwise,  player O must be less than player X.

If the number of X - number of O = 1, we need to check player O does not win. Otherwise, the game has stopped and player X cannot be greater than player O.

Code (Java):

?

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 63 64 65 66 67 68 69 70 71 72 73 74

class Solution {     public boolean validTicTacToe(String[] board) {         char[][] gameBoard = new char[3][3];                   for (int i = 0; i < 3; i++) {             gameBoard[i] = board[i].toCharArray();         }                   // Get number of X player and O player         //         int numOfX = 0;         int numOfO = 0;                   for (int i = 0; i < 3; i++) {             for (int j = 0; j < 3; j++) {                 char c = gameBoard[i][j];                                   if (c == 'X') {                     numOfX++;                 } else if (c == 'O') {                     numOfO++;                 }             }         }                   if (numOfX < numOfO || numOfX - numOfO > 1) {             return false;         }                   if (numOfX - numOfO == 1) {             if (hasWon(gameBoard, 'O')) {                 return false;             }         }                   if (numOfX == numOfO) {             if (hasWon(gameBoard, 'X')) {                 return false;             }         }                   return true;     }           private boolean hasWon(char[][] gameBoard, char player) {         for (int i = 0; i < 3; i++) {             if (gameBoard[i][0] == player &&                 gameBoard[i][1] == gameBoard[i][0] &&                 gameBoard[i][2] == gameBoard[i][1]) {                 return true;             }                           if (gameBoard[0][i] == player &&                 gameBoard[1][i] == gameBoard[0][i] &&                 gameBoard[2][i] == gameBoard[1][i]) {                 return true;             }                           if (player == gameBoard[0][0] &&                 gameBoard[0][0] == gameBoard[1][1] &&                 gameBoard[1][1] == gameBoard[2][2]) {                 return true;             }                           if (player == gameBoard[0][2] &&                 gameBoard[1][1] == gameBoard[0][2] &&                 gameBoard[1][1] == gameBoard[2][0]) {                 return true;             }         }                   return false;     } }