Welcome to Subscribe On Youtube

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.

  • 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;
        }
    }
    
    ############
    
    class Solution {
        private String[] board;
    
        public boolean validTicTacToe(String[] board) {
            this.board = board;
            int x = count('X'), o = count('O');
            if (x != o && x - 1 != o) {
                return false;
            }
            if (win('X') && x - 1 != o) {
                return false;
            }
            return !(win('O') && x != o);
        }
    
        private boolean win(char x) {
            for (int i = 0; i < 3; ++i) {
                if (board[i].charAt(0) == x && board[i].charAt(1) == x && board[i].charAt(2) == x) {
                    return true;
                }
                if (board[0].charAt(i) == x && board[1].charAt(i) == x && board[2].charAt(i) == x) {
                    return true;
                }
            }
            if (board[0].charAt(0) == x && board[1].charAt(1) == x && board[2].charAt(2) == x) {
                return true;
            }
            return board[0].charAt(2) == x && board[1].charAt(1) == x && board[2].charAt(0) == x;
        }
    
        private int count(char x) {
            int cnt = 0;
            for (var row : board) {
                for (var c : row.toCharArray()) {
                    if (c == x) {
                        ++cnt;
                    }
                }
            }
            return cnt;
        }
    }
    
  • // 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: List[str]) -> bool:
            def win(x):
                for i in range(3):
                    if all(board[i][j] == x for j in range(3)):
                        return True
                    if all(board[j][i] == x for j in range(3)):
                        return True
                if all(board[i][i] == x for i in range(3)):
                    return True
                return all(board[i][2 - i] == x for i in range(3))
    
            x = sum(board[i][j] == 'X' for i in range(3) for j in range(3))
            o = sum(board[i][j] == 'O' for i in range(3) for j in range(3))
            if x != o and x - 1 != o:
                return False
            if win('X') and x - 1 != o:
                return False
            return not (win('O') and x != o)
    
    ############
    
    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
    
  • func validTicTacToe(board []string) bool {
    	var x, o int
    	for _, row := range board {
    		for _, c := range row {
    			if c == 'X' {
    				x++
    			} else if c == 'O' {
    				o++
    			}
    		}
    	}
    	win := func(x byte) bool {
    		for i := 0; i < 3; i++ {
    			if board[i][0] == x && board[i][1] == x && board[i][2] == x {
    				return true
    			}
    			if board[0][i] == x && board[1][i] == x && board[2][i] == x {
    				return true
    			}
    		}
    		if board[0][0] == x && board[1][1] == x && board[2][2] == x {
    			return true
    		}
    		return board[0][2] == x && board[1][1] == x && board[2][0] == x
    	}
    	if x != o && x-1 != o {
    		return false
    	}
    	if win('X') && x-1 != o {
    		return false
    	}
    	return !(win('O') && x != o)
    }
    
  • /**
     * @param {string[]} board
     * @return {boolean}
     */
    var validTicTacToe = function (board) {
        function count(x) {
            let cnt = 0;
            for (const row of board) {
                for (const c of row) {
                    cnt += c == x;
                }
            }
            return cnt;
        }
        function win(x) {
            for (let i = 0; i < 3; ++i) {
                if (board[i][0] == x && board[i][1] == x && board[i][2] == x) {
                    return true;
                }
                if (board[0][i] == x && board[1][i] == x && board[2][i] == x) {
                    return true;
                }
            }
            if (board[0][0] == x && board[1][1] == x && board[2][2] == x) {
                return true;
            }
            return board[0][2] == x && board[1][1] == x && board[2][0] == x;
        }
        const [x, o] = [count('X'), count('O')];
        if (x != o && x - 1 != o) {
            return false;
        }
        if (win('X') && x - 1 != o) {
            return false;
        }
        return !(win('O') && x != o);
    };
    
    

All Problems

All Solutions