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

x
+
cmd
board = ["O "," "," "]

Output

x
+
cmd
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
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
board = ["O "," "," "]

Output

x
+
cmd
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
Copy The Code & Try With Live Editor

Input

x
+
cmd
board = ["XOX"," X "," "]

Output

x
+
cmd
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;
        }
    }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
board = ["XOX"," X "," "]

Output

x
+
cmd
false
Advertisements

Demonstration


Previous
#793 Leetcode Preimage Size of Factorial Zeroes Function Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#795 Leetcode Number of Subarrays with Bounded Maximum Solution in C, C++, Java, JavaScript, Python, C# Leetcode