794. Valid Tic-Tac-Toe State

T: O(n^2)
S: O(n)

class Solution {
    public boolean validTicTacToe(String[] board) {
        int n = board.length;
        int turns = 0;
        int[] rows = new int[n];
        int[] cols = new int[n];
        int diagnal = 0;
        int antiDiagnal = 0;
        boolean xwins = false;
        boolean owins = false;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // 對每個 board 的值做分析
                if (board[i].charAt(j) == 'X') {
                    turns++;
                    rows[i]++;
                    cols[j]++;
                    if (i == j) {
                        diagnal++;
                    }
                    if ((i+j) == n-1) {
                        antiDiagnal++;
                    }
                } else if (board[i].charAt(j) == 'O') {
                    turns--;
                    rows[i]--;
                    cols[j]--;
                    if (i == j) {
                        diagnal--;
                    }
                    if ((i+j) == n-1) {
                        antiDiagnal--;
                    }
                }
            }
        }
        
        for (int i = 0; i < n; i++) {
            xwins |= (rows[i] == n);
            xwins |= (cols[i] == n);   
        }
        xwins |= (diagnal == n);
        xwins |= (antiDiagnal == n);
        
        for (int i = 0; i < n; i++) {
            owins |= (rows[i] == -n);
            owins |= (cols[i] == -n);   
        }
        owins |= (diagnal == -n);
        owins |= (antiDiagnal == -n);
        
        // turns 在 win 時不是 1 就是 0, 其他狀況下會是其他值
        // ex: "O  ", "   ", "   " => turns = -1
        // ["XOX"," X ","   "] => turns = 2
        // ["XOX","O O","XOX"] => turns = 0, true
        // ["XOX","O  ","XOX"] => turns = 1, true
        // xwins 時應該是輪到 1不然不可能贏...同理 owins 時應該是輪到 0
        if (turns != 0 && turns != 1 || xwins && turns == 0 || owins && turns == 1) {
            return false;
        }
        return true;
    }
}

/*
這解法巧妙之處是 turns 0 or 1 代表快要成功了...amazing 
在檢查 xwins, owins 是不是快完成了 => ex: "OO " and "xx "and turns == 0 => true
因為是輪流下 o x的 所以能達成終局一定是 turns 很接近的狀況下, 不是 0 就是 1
*/

/*
T: O(n^2)
S: O(n)
*/