Problem statement

https://leetcode.com/problems/valid-tic-tac-toe-state/

Solution

Let us evaluate several characteristic of our board: number of O, number of X, number of full lines with X, which we call XXX and also OOO. Then board can be valid only in two cases:

  1. Number of X is one more than number of O, it means that last move was made by first: in this case OOO must be equal to zero and XXX should be less or equal than 2 (actually we do not need to check last condition)
  2. Number of X is equal to number of O, it means, that last move was made be second: in this case XXX must be equal to zero and OOO should be less or equal to 1 (again no need to check it in fact)

Complexity

Overall time complexity is O(n^2), where n = 3 is size of our grid, space complexity is the same.

Code

class Solution:
    def validTicTacToe(self, board):
        line = "".join(board)
        fin = [[0,1,2],[3,4,5],[6,7,8],[0,3,6],[1,4,7],[2,5,8],[0,4,8],[2,4,6]]
        XXX, OOO = 0, 0
        X, O = line.count("X"), line.count("O")
        
        for a,b,c in fin:
            XXX += (line[a] + line[b] + line[c] == "XXX")
            OOO += (line[a] + line[b] + line[c] == "OOO")
        
        if X - O == 1 and XXX <= 2 and OOO == 0: return True
        if X - O == 0 and OOO <= 1 and XXX == 0: return True
        
        return False