LeetCode Problem #794. Valid Tic-Tac-Toe State

Problem Statement:

Validate whether given three set of combination leads to valid Tic-Tac-Toe  pattern or not.

Given strings consists of 'x', 'o' or ' '.

Assume that game starts from 'x'. So, first players1 puts 'x' in the game then player2 takes the turn and inserts 'o'. The game will continue until one of the players win.

Our task is to find out whether given pattern is possible at any point of time of play. Return true if the given pattern is possible else return false.

Example 1:

Input:

['XXX', '   ', 'OOO']

Output:

 false

Explanation:

The given pattern is not possible because once the player 1 put three X in a row which is in the first row game is over, player 2 doesn't get a chance to put thrid O. So, this pattern is not possible.

Example 2:

Input:

['XOX', 'OOX ', 'XO ']

Output:

 true

Explanation:

The given pattern is possible.

Example 3:

Input:

['OXX', 'XOX', 'OXO']

Output:

 false

Explanation:

The given pattern is not possible because once the player 2 inserts O in diagonal manner, there is no chance for player one to insert one more X

Example 4:

Input:

['   ', '   ', '   ']

Output:

 true

Explanation:

This is the first step in the game where players start.

Approach to the Solution:

1. To solve this problem one of the easy way would be to eliminate all the wrong possibilities.
2. Here are the list of wrong possibilities:
• Number of O is greater than number of X
• Number of X is greater than number of O + 1
• Games continue even after someone win.
3. So, the solution would be: First count the number of X and number of O
4. Compare the X and O as per the above conditions if any one of them is true return false as such pattern is not possible.
5. Then find out whether game is completed by any player or not. If game is completed them save who won the game.
6. Whether game is completed or not can be checked by comparing rows and columns

Solution in C++:

class Solution {
public:
    bool validTicTacToe(vector<string>& board) {
        int x = GetCharCount(board, 'X');
        int o = GetCharCount(board, 'O');
        
        if(x < o || x > o + 1)
            return false;
        bool is_o_bingo = false;
        if(IsBingo(board, is_o_bingo)){
            if((is_o_bingo && x != o)  || (!is_o_bingo && x == o))
            return false;
        }
        return true;
    }
    
private:
    bool IsBingo(vector<string> board, bool &is_o_bingo){
        //top row middle
        if(board[0][0] != ' ' && board[0][0] == board[0][1] && board[0][0] == board[0][2]){
            if(board[0][0] == 'O')
                is_o_bingo = true;
            return true;
        }
        // left column middle
        else if(board[0][0] != ' ' && board[0][0] == board[1][0] && board[0][0] == board[2][0]){
            if(board[0][0] == 'O')
                is_o_bingo = true;
            return true;
        }
        // bottom row middle
        else if(board[2][0] != ' ' && board[2][0] == board[2][1] && board[2][0] == board[2][2]){
            if(board[2][0] == 'O')
                is_o_bingo = true;
            return true;
        }
        // right column middle
        else if(board[0][2] != ' ' && board[0][2] == board[1][2] && board[0][2] == board[2][2]){
            if(board[0][2] == 'O')
                is_o_bingo = true;
            return true;
        }
        // middle column
        else if(board[1][1] != ' ' && board[1][1] == board[0][1] && board[1][1] == board[2][1]){
            if(board[1][1] == 'O')
                is_o_bingo = true;
            return true;
        }
        // middle row
        else if(board[1][1] != ' ' && board[1][1] == board[1][0] && board[1][1] == board[1][2]){
            if(board[1][1] == 'O')
                is_o_bingo = true;
            return true;
        }
        //diagonal elements
        else if(board[1][1] != ' ' && board[1][1] == board[0][0] && board[1][1] == board[2][2]){
            if(board[1][1] == 'O')
                is_o_bingo = true;
            return true;
        }
        //another diagonal
        else if(board[1][1] != ' ' && board[1][1] == board[2][0] && board[1][1] == board[0][2]){
            if(board[1][1] == 'O')
                is_o_bingo = true;
            return true;
        }
        return false;
    }
    int GetCharCount(vector<string> board, char c){
            int count = 0;
        for(int iter = 0; iter < board.size(); ++iter){
            for(int i = 0; i < board[iter].length(); ++i){
                if(board[iter][i] == c)
                    ++count;
            }
        }
        return count;
    }
};