Valid Tic-Tac-Toe State Problem


Description

LeetCode Problem 794.

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:

1
2
3
Input: board = ["O  ","   ","   "]
Output: false
Explanation: The first player always plays "X".

Example 2:

1
2
3
Input: board = ["XOX"," X ","   "]
Output: false
Explanation: Players take turns making moves.

Example 3:

1
2
Input: board = ["XXX","   ","OOO"]
Output: false

Example 4:

1
2
Input: board = ["XOX","O O","XOX"]
Output: true

Constraints:

  • board.length == 3
  • board[i].length == 3
  • board[i][j] is either ‘X’, ‘O’, or ‘ ‘.


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    bool iswin(vector<string> &board, char c) {
        return ((board[0][0] == c && board[0][1] == c && board[0][2] == c) ||
          (board[1][0] == c && board[1][1] == c && board[1][2] == c) ||
          (board[2][0] == c && board[2][1] == c && board[2][2] == c) ||
          (board[0][0] == c && board[1][0] == c && board[2][0] == c) ||
          (board[0][1] == c && board[1][1] == c && board[2][1] == c) ||
          (board[0][2] == c && board[1][2] == c && board[2][2] == c) ||
          (board[0][0] == c && board[1][1] == c && board[2][2] == c) ||
          (board[0][2] == c && board[1][1] == c && board[2][0] == c));
    }
    
    bool validTicTacToe(vector<string>& board) {
        int xcnt = 0, ocnt = 0;
        for (string s: board) {
            for (char c: s) {
                if (c == 'X') 
                    xcnt ++;
                else if (c == 'O') 
                    ocnt ++;
            }
        }
        if (xcnt != ocnt && xcnt != ocnt + 1) 
            // X can have equal or only 1 more move than O
            return false;          
        if (iswin(board, 'X') && xcnt != ocnt + 1) 
            // X will win by having one additional move
            return false;     
        if (iswin(board, 'O') && xcnt != ocnt) 
            // since X played first, O can win only when both have made same number of moves
            return false;         
        return true;
    }
};




Related Posts

String Without Aaa Or Bbb Problem

LeetCode 984. Given two integers a and b, return any...

Shifting Letters Problem

LeetCode 848. You are given a string s of lowercase...

Positions Of Large Groups Problem

LeetCode 830. In a string sof lowercase letters, these letters...

Orderly Queue Problem

LeetCode 899. You are given a string s and an...

Number Of Lines To Write String Problem

LeetCode 806. You are given a string s of lowercase...

Masking Personal Information Problem

LeetCode 831. You are given a personal information string s,...