Algorithm
Problem Name: 794. Valid Tic-Tac-Toe State
Given a Tic-Tac-Toe board 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 that 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 three 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 = ["XOX","O O","XOX"] Output: true
Constraints:
board.length == 3
board[i].length == 3
board[i][j]
is either'X'
,'O'
, or' '
.
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public boolean validTicTacToe(String[] board) {
if (hasWon(board, 'X')) {
return getCount(board, 'X') - getCount(board, 'O') == 1;
}
if (hasWon(board, 'O')) {
return getCount(board, 'X') - getCount(board, 'O') == 0;
}
int diff = getCount(board, 'O') - getCount(board, 'X');
return diff == 0 || diff == -1;
}
private boolean hasWon(String[] board, char player) {
boolean b1 = (board[0].charAt(0) == player && board[0].charAt(1) == player && board[0].charAt(2) == player);
boolean b2 = (board[0].charAt(0) == player && board[1].charAt(0) == player && board[2].charAt(0) == player);
boolean b3 = (board[0].charAt(1) == player && board[1].charAt(1) == player && board[2].charAt(1) == player);
boolean b4 = (board[0].charAt(2) == player && board[1].charAt(2) == player && board[2].charAt(2) == player);
boolean b5 = (board[0].charAt(0) == player && board[1].charAt(1) == player && board[2].charAt(2) == player);
boolean b6 = (board[0].charAt(2) == player && board[1].charAt(1) == player && board[2].charAt(0) == player);
boolean b7 = (board[1].charAt(0) == player && board[1].charAt(1) == player && board[1].charAt(2) == player);
boolean b8 = (board[2].charAt(0) == player && board[2].charAt(1) == player && board[2].charAt(2) == player);
return b1 || b2 || b3 || b4 || b5|| b6 || b7 || b8;
}
private int getCount(String[] board, char player) {
int count = 0;
for (String row : board) {
for (char c : row.toCharArray()) {
if (c == player) {
count++;
}
}
}
return count;
}
}
Copy The Code &
Try With Live Editor
Input
Output
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const validTicTacToe = function(board) {
if (board.length == 0) return false
// turns = 0 represents 'X' will move, otherwise, 'O' will move
let turns = 0
// check whether 'X' wins or 'O' wins, or no players win
let xWin = isGameOver(board, 'X')
let oWin = isGameOver(board, 'O')
for (let i = 0; i < board.length; i++) {
for (let j = 0; j < board[0].length; j++) {
if (board[i].charAt(j) == 'X') turns++
else if (board[i].charAt(j) == 'O') turns--
}
}
if (turns < 0 || turns > 1 || (turns == 0 && xWin) || (turns == 1 && oWin))
return false
return true
}
function isGameOver(board, player) {
// check horizontal
for (let i = 0; i < 3; i++) {
if (
board[i].charAt(0) === player &&
board[i].charAt(0) === board[i].charAt(1) &&
board[i].charAt(1) === board[i].charAt(2)
) {
return true
}
}
// check vertical
for (let j = 0; j < 3; j++) {
if (
board[0].charAt(j) == player &&
board[0].charAt(j) == board[1].charAt(j) &&
board[1].charAt(j) == board[2].charAt(j)
) {
return true
}
}
// check diagonal
if (
board[1].charAt(1) == player &&
((board[0].charAt(0) == board[1].charAt(1) &&
board[1].charAt(1) == board[2].charAt(2)) ||
(board[0].charAt(2) == board[1].charAt(1) &&
board[1].charAt(1) == board[2].charAt(0)))
) {
return true
}
return false
}
Copy The Code &
Try With Live Editor
Input
Output
#3 Code Example with Python Programming
Code -
Python Programming
class Solution(object):
def check_win_positions(self, board, player):
"""
Check if the given player has a win position.
Return True if there is a win position. Else return False.
"""
#Check the rows
for i in range(len(board)):
if board[i][0] == board[i][1] == board[i][2] == player:
return True
#Check the columns
for i in range(len(board)):
if board[0][i] == board[1][i] == board[2][i] == player:
return True
#Check the diagonals
if board[0][0] == board[1][1] == board[2][2] == player or \u005C
board[0][2] == board[1][1] == board[2][0] == player:
return True
return False
def validTicTacToe(self, board):
"""
:type board: List[str]
:rtype: bool
"""
x_count, o_count = 0, 0
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] == "X":
x_count += 1
elif board[i][j] == "O":
o_count += 1
if o_count > x_count or x_count-o_count>1:
return False
if self.check_win_positions(board, 'O'):
if self.check_win_positions(board, 'X'):
return False
return o_count == x_count
if self.check_win_positions(board, 'X') and x_count!=o_count+1:
return False
return True
Copy The Code &
Try With Live Editor
Input
Output
#4 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _0794_ValidTicTacToeState
{
public bool ValidTicTacToe(string[] board)
{
int xCount = 0, oCount = 0;
foreach (string row in board)
foreach (char ch in row)
{
if (ch == 'X') xCount++;
if (ch == 'O') oCount++;
}
if (oCount != xCount && oCount != xCount - 1) return false;
if (Win(board, 'X') && oCount != xCount - 1) return false;
if (Win(board, 'O') && oCount != xCount) return false;
return true;
}
private bool Win(string[] board, char ch)
{
for (int i = 0; i < 3; ++i)
{
if (ch == board[0][i] && ch == board[1][i] && ch == board[2][i])
return true;
if (ch == board[i][0] && ch == board[i][1] && ch == board[i][2])
return true;
}
if (ch == board[0][0] && ch == board[1][1] && ch == board[2][2])
return true;
if (ch == board[0][2] && ch == board[1][1] && ch == board[2][0])
return true;
return false;
}
}
}
Copy The Code &
Try With Live Editor
Input
Output