题目重点：Phone Coding 题目只说 LC794 的扩展版；本文明确只解标准 3×3 轮流落子、胜后即停的状态校验，扩展规则列入待核。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版为标准 3×3 棋盘，X 先手、X/O 轮流每次落一格；已有玩家胜利时立即停止，不能继续落子。
- 输入是三行长度 3 的字符串，仅允许 X、O、空格；返回布尔值，不负责给出具体落子序列。扩展版可能不满足这些规则，需另核原题。
解题路线
- 先检查棋盘形状和字符集合；数 X/O，合法轮次只能 X=O 或 X=O+1。
- 检查 8 条获胜线，X 与 O 不能同时获胜；若 X 获胜必须 X=O+1，若 O 获胜必须 X=O。
- 这些条件对标准规则也是充分的：合法轮次和赢家最后一步可构造一条未提前结束的落子序列；若担心证明，训练测试用完整状态图枚举佐证。
- 从空棋盘 BFS 生成所有合法落子状态，赢家出现即停止；把 3^9=19,683 种板面全部与条件判断对照，得到 5,478 个可达状态。
手动走一遍
['XXX','OO ',' '] 有 X=3/O=2 且 X 胜，合法；['XXX','OOO',' '] 双方同时胜，非法；['XXX','OO ',' O'] 有 X=3/O=3，轮次计数本身允许，但 X 获胜不可能是 O 刚下完的状态，也非法。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Validate standard 3x3 Tic-Tac-Toe states; source extension unspecified."""
LINES = ((0, 1, 2), (3, 4, 5), (6, 7, 8),
(0, 3, 6), (1, 4, 7), (2, 5, 8),
(0, 4, 8), (2, 4, 6))
def valid_state(rows: list[str]) -> bool:
if len(rows) != 3 or any(len(row) != 3 for row in rows):
return False
board = "".join(rows)
if any(cell not in "XO " for cell in board):
return False
x = board.count("X")
o = board.count("O")
if x != o and x != o + 1:
return False
x_win = any(all(board[i] == "X" for i in line) for line in LINES)
o_win = any(all(board[i] == "O" for i in line) for line in LINES)
if x_win and o_win:
return False
if x_win and x != o + 1:
return False
if o_win and x != o:
return False
return True
复杂度
固定 3×3 棋盘只检查 9 格和 8 条胜利线，为 O(1) 时间/空间；若扩展到 N×N 与 K 连线，胜线枚举和轮次充分性都需重推，不能直接照搬常数复杂度。
易错点与追问
容易失分的边界
- 只检查 X/O 数量，漏掉双赢或赢家与落子数不符。
- 允许胜利后继续落子。
- 把一篇只说 LC794 扩展版的题目写成完整扩展规则。
- 把标准 3×3 的充分条件未经证明套到任意大棋盘与胜利长度。
继续深挖
- 若棋盘改成 N×N、连 K 获胜，如何判定状态可达？
- 若要返回一条合法落子序列，需做回溯还是可构造？
- 如果允许胜后继续落子，上述条件哪些会改变？
- 题目所说扩展到底是规则、尺寸还是输出形式？
