Algorithm
Problem Name: 794. Valid Tic-Tac-Toe State
Problem Link: https://leetcode.com/problems/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 == 3board[i].length == 3board[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;
}
}
Input
board = ["O "," "," "]
Output
false
#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
}
Input
board = ["O "," "," "]
Output
false
#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
Input
board = ["XOX"," X "," "]
Output
false
#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;
}
}
}
Input
board = ["XOX"," X "," "]
Output
false