Formatted question description: https://leetcode.ca/all/794.html

794. Valid Tic-Tac-Toe State (Medium)

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 string board[i] has length 3.
  • Each board[i][j] is a character in the set {" ", "X", "O"}.

Solution 1.

// OJ: https://leetcode.com/problems/valid-tic-tac-toe-state/
// Time: O(1)
// Space: O(1)
class Solution {
private:
    int count(vector<string>& board, char target){ 
        int cnt = 0;
        for (auto row : board) {
            for (char c : row) {
                if (c == target) ++cnt;
            }
        }
        return cnt;
    }
    bool testWin(vector<string>& board, char target) {
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                if (board[i][j] != target) break;
                if (j == 2) return true;
            }
        }
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                if (board[j][i] != target) break;
                if (j == 2) return true;
            }
        }
        for (int i = 0; i < 3; ++i) {
            if (board[i][i] != target) break;
            if (i == 2) return true;
        }
        for (int i = 0; i < 3; ++i) {
            if (board[i][2 - i] != target) break;
            if (i == 2) return true;
        }
        return false;
    }
public:
    bool validTicTacToe(vector<string>& board) {
        int xCnt = count(board, 'X');
        int oCnt = count(board, 'O');
        if (xCnt != oCnt && xCnt != oCnt + 1) return false;
        bool xWin = testWin(board, 'X');
        bool oWin = testWin(board, 'O');
        if (xWin && oWin) return false;
        if (!xWin && !oWin) return true;
        return (xWin && xCnt == oCnt + 1) || (oWin && xCnt == oCnt);
    }
};

Java

  • class Solution {
        public boolean validTicTacToe(String[] board) {
            int xCount = 0, oCount = 0;
            for (String row: board) {
                for (char c: row.toCharArray()) {
                    if (c == 'X')
                        xCount++;
                    if (c == '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;
        }
    
        public boolean win(String[] B, char P) {
            for (int i = 0; i < 3; i++) {
                if (P == B[0].charAt(i) && P == B[1].charAt(i) && P == B[2].charAt(i))
                    return true;
                if (P == B[i].charAt(0) && P == B[i].charAt(1) && P == B[i].charAt(2))
                    return true;
            }
            if (P == B[0].charAt(0) && P == B[1].charAt(1) && P == B[2].charAt(2))
                return true;
            if (P == B[0].charAt(2) && P == B[1].charAt(1) && P == B[2].charAt(0))
                return true;
            return false;
        }
    }
    
  • // OJ: https://leetcode.com/problems/valid-tic-tac-toe-state/
    // Time: O(1)
    // Space: O(1)
    class Solution {
    private:
        int count(vector<string>& board, char target){ 
            int cnt = 0;
            for (auto row : board) {
                for (char c : row) {
                    if (c == target) ++cnt;
                }
            }
            return cnt;
        }
        bool testWin(vector<string>& board, char target) {
            for (int i = 0; i < 3; ++i) {
                for (int j = 0; j < 3; ++j) {
                    if (board[i][j] != target) break;
                    if (j == 2) return true;
                }
            }
            for (int i = 0; i < 3; ++i) {
                for (int j = 0; j < 3; ++j) {
                    if (board[j][i] != target) break;
                    if (j == 2) return true;
                }
            }
            for (int i = 0; i < 3; ++i) {
                if (board[i][i] != target) break;
                if (i == 2) return true;
            }
            for (int i = 0; i < 3; ++i) {
                if (board[i][2 - i] != target) break;
                if (i == 2) return true;
            }
            return false;
        }
    public:
        bool validTicTacToe(vector<string>& board) {
            int xCnt = count(board, 'X');
            int oCnt = count(board, 'O');
            if (xCnt != oCnt && xCnt != oCnt + 1) return false;
            bool xWin = testWin(board, 'X');
            bool oWin = testWin(board, 'O');
            if (xWin && oWin) return false;
            if (!xWin && !oWin) return true;
            return (xWin && xCnt == oCnt + 1) || (oWin && xCnt == oCnt);
        }
    };
    
  • class Solution:
        def validTicTacToe(self, board):
            """
            :type board: List[str]
            :rtype: bool
            """
            xCount, oCount = 0, 0
            for i in range(3):
                for j in range(3):
                    if board[i][j] == 'O':
                        oCount += 1
                    elif board[i][j] == 'X':
                        xCount += 1
            if oCount != xCount and oCount != xCount - 1: return False
            if oCount != xCount and self.win(board, 'O'): return False
            if oCount != xCount - 1 and self.win(board, 'X'): return False
            return True
            
        def win(self, board, P):
            # board is list[str]
            # P is 'X' or 'O' for two players
            for j in range(3):
                if all(board[i][j] == P for i in range(3)): return True
                if all(board[j][i] == P for i in range(3)): return True
            if board[0][0] == board[1][1] == board[2][2] == P: return True
            if board[0][2] == board[1][1] == board[2][0] == P: return True
            return False
    

All Problems

All Solutions