Skip to content

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<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 += ranges::count(row, c);

    return ans;
  }

  bool isWinned(const vector<string>& board, char c) {
    vector<string> rotated = rotate(board);

    auto equalsToThree = [&c](const string& row) {
      return ranges::count(row, c) == 3;
    };

    return ranges::any_of(board, equalsToThree) ||
           ranges::any_of(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;
  }
};

 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: str) -> 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