<p>Given a Tic-Tac-Toe board as a string array <code>board</code>, return <code>true</code> if and only if it is possible to reach this board position during the course of a valid tic-tac-toe game.</p>

<p>The board is a <code>3 x 3</code> array that consists of characters <code>&#39; &#39;</code>, <code>&#39;X&#39;</code>, and <code>&#39;O&#39;</code>. The <code>&#39; &#39;</code> character represents an empty square.</p>

<p>Here are the rules of Tic-Tac-Toe:</p>

<ul>
	<li>Players take turns placing characters into empty squares <code>&#39; &#39;</code>.</li>
	<li>The first player always places <code>&#39;X&#39;</code> characters, while the second player always places <code>&#39;O&#39;</code> characters.</li>
	<li><code>&#39;X&#39;</code> and <code>&#39;O&#39;</code> characters are always placed into empty squares, never filled ones.</li>
	<li>The game ends when there are three of the same (non-empty) character filling any row, column, or diagonal.</li>
	<li>The game also ends if all squares are non-empty.</li>
	<li>No more moves can be played if the game is over.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/05/15/tictactoe1-grid.jpg" style="width: 253px; height: 253px;" />
<pre>
<strong>Input:</strong> board = [&quot;O  &quot;,&quot;   &quot;,&quot;   &quot;]
<strong>Output:</strong> false
<strong>Explanation:</strong> The first player always plays &quot;X&quot;.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/05/15/tictactoe2-grid.jpg" style="width: 253px; height: 253px;" />
<pre>
<strong>Input:</strong> board = [&quot;XOX&quot;,&quot; X &quot;,&quot;   &quot;]
<strong>Output:</strong> false
<strong>Explanation:</strong> Players take turns making moves.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/05/15/tictactoe4-grid.jpg" style="width: 253px; height: 253px;" />
<pre>
<strong>Input:</strong> board = [&quot;XOX&quot;,&quot;O O&quot;,&quot;XOX&quot;]
<strong>Output:</strong> true
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>board.length == 3</code></li>
	<li><code>board[i].length == 3</code></li>
	<li><code>board[i][j]</code> is either <code>&#39;X&#39;</code>, <code>&#39;O&#39;</code>, or <code>&#39; &#39;</code>.</li>
</ul>

class Solution:
    def validTicTacToe(self, board: List[str]) -> bool:
        '''
        TC: O(3*3) for checking valid state
        SC: O(1) if we don't count input as extra space
        Insight:
        Since 'X' always play first, we need to guarantee below conditions:
            1. the number of 'X' must be larger than one or equal to the number of 'O'
            2. if winner is 'X', the number of 'X' must be equal to the number of 'O' +1
               if winner is 'O', the number of 'O' must be equal to the number of 'X'
        '''
        ###count 'X' and 'O'
        count_X, count_O = 0, 0
        for s in board: 
            for c in s:
                if c=='X':
                    count_X+=1
                elif c=='O':
                    count_O+=1
        if count_O not in {count_X, count_X-1}: ##case1
            return False
        ###check winner
        def isWinner(player):
            for i in range(3):
                if board[i][0]==board[i][1]==board[i][2]==player: ##check row
                    return True
            for i in range(3):
                if board[0][i]==board[1][i]==board[2][i]==player: ##check col
                    return True 
            if board[0][0]==board[1][1]==board[2][2]==player: ##check diag (topleft to bottomright)
                return True
            if board[2][0]==board[1][1]==board[0][2]==player: ##check diag (bottomleft to topright)
                return True
            return False
        if isWinner('X') and count_X-count_O!=1: ##case2
            return False
        if isWinner('O') and count_X-count_O!=0:
            return False
        return True
        
38