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 stringboard[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):
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; } }
No comments:
Post a Comment