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:

## 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.

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

Comment
Junhao Wang
Hi, I was a master student at USC studying Computer Science.