LeetCode 794. Valid Tic-Tac-Toe State [Swift 题解]

题目

A Tic-Tac-Toe board is given as a string array board. Return True if and only if it is possible to reach this board position during the course of a valid tic-tac-toe game.

The board is a 3 x 3 array, and consists of characters " ", "X", and "O". The " " character represents an empty square.

Here are the rules of Tic-Tac-Toe:

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

Example 1:  
Input: board = ["O  ", "   ", "   "]  
Output: false  
Explanation: The first player always plays "X".

Example 2:  
Input: board = ["XOX", " X ", "   "]  
Output: false  
Explanation: Players take turns making moves.

Example 3:  
Input: board = ["XXX", "   ", "OOO"]  
Output: false

Example 4:  
Input: board = ["XOX", "O O", "XOX"]  
Output: true  

思路

有几个限制条件: X先走, O后走. 所以如果看X,O个数的话O <= X <=(O+1)
X和O不可能同时赢.
还有另外两个容易忽略的条件是: 如果X赢的话, xCount = oCount + 1 如果O赢的话, xCount = oCount

func validTicTacToe(_ board: [String]) -> Bool {  
        let x = Character("X")
        let o = Character("O")

        let size = 3
        var rowCount = Array(repeating: 0, count: size)
        var colCount = Array(repeating: 0, count: size)
        var diagCount = 0
        var antiDiagCount = 0

        var xCount = 0
        var oCount = 0

        for (rowIndex, str) in board.enumerated() {
            for (colIndex, char) in str.enumerated() {
                switch char {
                case x:
                    rowCount[rowIndex] += 1
                    colCount[colIndex] += 1
                    if rowIndex == colIndex {
                        diagCount += 1
                    }
                    if (rowIndex + colIndex) == (size - 1) {
                        antiDiagCount += 1
                    }
                    xCount += 1
                case o:
                    rowCount[rowIndex] -= 1
                    colCount[colIndex] -= 1
                    if rowIndex == colIndex {
                        diagCount -= 1
                    }
                    if (rowIndex + colIndex) == (size - 1) {
                        antiDiagCount -= 1
                    }
                    oCount += 1
                default: break
                }
            }
        }

        //x >= o
        let validCount = oCount...(oCount + 1) ~= xCount
        if !validCount {
            return false
        }

        let wins = rowCount + colCount + [diagCount, antiDiagCount]
        var xWin = false
        var oWin = false
        for count in wins {
            if count == size {
                xWin = true
            }
            if count == (0 - size) {
                oWin = true
            }
        }

        switch (xWin, oWin) {
        case (true, true):
            return false
        case (true, false):
            return xCount > oCount
        case (false, true):
            return xCount == oCount
        default:
            return true
        }
    }

chenbo

编程爱好者

Singapore