LeetCode Solutions

794. Valid Tic-Tac-Toe State

Time:

Space:

			

class Solution {
 public:
  bool validTicTacToe(vector<string>& 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<string>& board, char c) {
    int ans = 0;

    for (const string& row : board)
      ans += count(begin(row), end(row), c);

    return ans;
  }

  bool isWinned(const vector<string>& board, char c) {
    vector<string> 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<string> rotate(const vector<string>& board) {
    vector<string> rotated(3);

    for (const string& row : board)
      for (int i = 0; i < 3; ++i)
        rotated[i].push_back(row[i]);

    return rotated;
  }
};
			

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;
  }
}
			

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