What is the main algorithmic pattern in the 'Valid Tic-Tac-Toe State' problem?

The main pattern involves validating the game board by counting moves, checking for winners, and ensuring the sequence of turns is correct.

What are the most common mistakes when solving the 'Valid Tic-Tac-Toe State' problem?

The most common mistakes include counting 'X' and 'O' moves incorrectly or failing to correctly handle the game’s alternating turns.

Can I solve the 'Valid Tic-Tac-Toe State' problem with a brute force approach?

While a brute force approach is possible, it's generally inefficient. The problem can be solved efficiently by directly checking row, column, and diagonal patterns.

How does GhostInterview help me with 'Valid Tic-Tac-Toe State'?

GhostInterview guides you through step-by-step validation, helping you identify errors in the board state and ensuring you follow the correct game rules.

Are there any variations of the 'Valid Tic-Tac-Toe State' problem?

Yes, variations can include larger grids or different rules, such as a non-square board or a 3D Tic-Tac-Toe version.

#794

Medium

auto_awesome数组·matrix

LeetCode 题解工作台

有效的井字游戏

给你一个字符串数组 board 表示井字游戏的棋盘。当且仅当在井字游戏过程中，棋盘有可能达到 board 所显示的状态时，才返回 true 。井字游戏的棋盘是一个 3 x 3 数组，由字符 ' ' ， 'X' 和 'O' 组成。字符 ' ' 代表一个空位。以下是井字游戏的规则：玩家轮流将字符放…

数组矩阵

题目描述

给你一个字符串数组 board 表示井字游戏的棋盘。当且仅当在井字游戏过程中，棋盘有可能达到 board 所显示的状态时，才返回 true 。

井字游戏的棋盘是一个 3 x 3 数组，由字符 ' '，'X' 和 'O' 组成。字符 ' ' 代表一个空位。

以下是井字游戏的规则：

玩家轮流将字符放入空位（' '）中。
玩家 1 总是放字符 'X' ，而玩家 2 总是放字符 'O' 。
'X' 和 'O' 只允许放置在空位中，不允许对已放有字符的位置进行填充。
当有 3 个相同（且非空）的字符填充任何行、列或对角线时，游戏结束。
当所有位置非空时，也算为游戏结束。
如果游戏结束，玩家不允许再放置字符。

示例 1：

输入：board = ["O  ","   ","   "]
输出：false
解释：玩家 1 总是放字符 "X" 。

示例 2：

输入：board = ["XOX"," X ","   "]
输出：false
解释：玩家应该轮流放字符。

示例 3:

输入：board = ["XOX","O O","XOX"]
输出：true

提示：

board.length == 3
board[i].length == 3
board[i][j] 为 'X'、'O' 或 ' '

lightbulb

解题思路

方法一：分类讨论

我们先统计当前棋盘上 'X' 和 'O' 的数量，记为 $x$ 和 $o$ 。接下来，我们分情况讨论：

如果 $x \neq o$ 且 $x - 1 \neq o$ ，则当前棋盘不可能是有效棋盘，返回 false。
如果当前棋盘上玩家 1 获胜，但 $x-1 \neq o$ ，则当前棋盘不可能是有效棋盘，返回 false。
如果当前棋盘上玩家 2 获胜，但 $x \neq o$ ，则当前棋盘不可能是有效棋盘，返回 false。
其他情况下，当前棋盘是有效棋盘，返回 true。

时间复杂度 $O(C)$ ，空间复杂度 $O(1)$ 。其中 $C$ 是棋盘上的格子数。本题中 $C = 9$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def validTicTacToe(self, board: List[str]) -> bool:
        def win(x):
            for i in range(3):
                if all(board[i][j] == x for j in range(3)):
                    return True
                if all(board[j][i] == x for j in range(3)):
                    return True
            if all(board[i][i] == x for i in range(3)):
                return True
            return all(board[i][2 - i] == x for i in range(3))

        x = sum(board[i][j] == 'X' for i in range(3) for j in range(3))
        o = sum(board[i][j] == 'O' for i in range(3) for j in range(3))
        if x != o and x - 1 != o:
            return False
        if win('X') and x - 1 != o:
            return False
        return not (win('O') and x != o)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate correctly identify when the board counts for 'X' and 'O' are invalid?
question_mark
Is the candidate able to logically check for a valid winner without errors?
question_mark
Does the candidate understand the alternating move sequence and its effect on validity?

warning

常见陷阱

外企场景

error
Forgetting to account for the fact that 'X' always starts first.
error
Overlooking the case where both players are declared winners simultaneously.
error
Incorrectly counting moves, leading to an invalid board state.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider larger boards or different-sized Tic-Tac-Toe grids for extension of the problem.
arrow_right_alt
Validate different sets of rules for non-standard Tic-Tac-Toe games.
arrow_right_alt
Check for invalid inputs or malformed boards as an edge case.

help

常见问题

外企场景

继续练习

#803 打砖块 #782 变为棋盘 #807 保持城市天际线