# 794. Valid Tic-Tac-Toe State

• Time:
• Space:
  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 36 37 38 39 40 41 42 43 44 45 46 47 48 class Solution { public: bool validTicTacToe(vector& board) { const int countX = sum(board, 'X'); const int countO = sum(board, 'O'); if (countX < countO || countX - countO > 1) return false; if (isWinned(board, 'X') && countX == countO || isWinned(board, 'O') && countX != countO) return false; return true; } private: int sum(const vector& board, char c) { int ans = 0; for (const string& row : board) ans += count(begin(row), end(row), c); return ans; } bool isWinned(const vector& board, char c) { vector rotated = rotate(board); auto equalsToThree = [&c](const string& row) { return count(begin(row), end(row), c) == 3; }; return any_of(begin(board), end(board), equalsToThree) || any_of(begin(rotated), end(rotated), equalsToThree) || board[0][0] == c && board[1][1] == c && board[2][2] == c || board[0][2] == c && board[1][1] == c && board[2][0] == c; } vector rotate(const vector& board) { vector rotated(3); for (const string& row : board) for (int i = 0; i < 3; ++i) rotated[i].push_back(row[i]); return rotated; } }; 
  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 36 37 38 39 40 41 42 class Solution { public boolean validTicTacToe(String[] board) { final int countX = sum(board, 'X'); final int countO = sum(board, 'O'); if (countX < countO || countX - countO > 1) return false; if (isWinned(board, 'X') && countX == countO || isWinned(board, 'O') && countX != countO) return false; return true; } private int sum(final String[] board, char c) { int ans = 0; for (final String row : board) ans += row.chars().filter(i -> i == c).count(); return ans; } private boolean isWinned(final String[] board, char c) { String[] rotated = rotate(board); return Arrays.stream(board).anyMatch(row -> row.chars().filter(i -> i == c).count() == 3) || Arrays.stream(rotated).anyMatch(row -> row.chars().filter(i -> i == c).count() == 3) || board[0].charAt(0) == c && board[1].charAt(1) == c && board[2].charAt(2) == c || board[0].charAt(2) == c && board[1].charAt(1) == c && board[2].charAt(0) == c; } private String[] rotate(final String[] board) { String[] rotated = new String[3]; for (final String row : board) for (int i = 0; i < 3; ++i) rotated[i] += row.charAt(i); return rotated; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution: def validTicTacToe(self, board: List[str]) -> bool: def isWin(c: chr) -> bool: return any(row.count(c) == 3 for row in board) or \ any(row.count(c) == 3 for row in list(zip(*board))) or \ all(board[i][i] == c for i in range(3)) or \ all(board[i][2 - i] == c for i in range(3)) countX = sum(row.count('X') for row in board) countO = sum(row.count('O') for row in board) if countX < countO or countX - countO > 1: return False if isWin('X') and countX == countO or isWin('O') and countX != countO: return False return True