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

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

Have you met this question in a real interview?  

Example

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

bool validTicTacToe(vector<string> &board) { // Write your code // 几种情况 挨个分析. // 等找一个helper 函数，在可举出的例子很多时，一定要重新定义一个函数，来辅助。 // 否则，代码太长。这也是实际面试中会出现的情况 int numO = 0; int numX = 0; for(int i = 0; i < 3; i++){ for(int j = 0; j < 3; j++){ if(board[i][j] == 'O'){ numO++; } if(board[i][j] == 'X'){ numX++; } } } if(!(numO == numX || numX == numX + 1)){ return false; } if(numO == numX && win(board, 'X')){ return false; } if(numO + 1 == numX && win(board, 'O')){ return false; } return true; } bool win(vector<string>& board, char ch) { for (int i = 0; i < 3; i++) { if (board[i][0] == board[i][1] && board[i][0] == board[i][2] && board[i][0] == ch ) { return true; } } for (int j = 0; j < 3; j++) { if (board[0][j] == board[1][j] && board[0][j] == board[2][j] && board[0][j] == ch ) { return true; } } if (board[0][0] == board[1][1] && board[0][0] == board[2][2] && board[0][0] == ch ) { return true; } if (board[0][2] == board[1][1] && board[0][2] == board[2][0] && board[0][2] == ch ) { return true; } return false; }