Leetcode 36 Solution

This article provides solution to leetcode question 36 (valid-sudoku)
Categories:
Tags:
Access this page by simply typing in "lcs 36" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/valid-sudoku

Thinking Process

Very basic question, just use bit operation to check if there is any conflicting numbers.

Solution

class Solution {
public:
    bool isValidArray(const vector<char>& a)
    {
        if (a.size() != 9)
            return false;



        uint32_t b = 0;



        for (int i = 0; i < a.size(); i++)
        {
            if (a[i] == '.')
                continue;



            if (a[i] < '1' || a[i] > '9')
                return false;



            int val = a[i] - '0';



            if ((b & (1 << val)))
                return false;



            b |= (1 << val);
        }



        return true;
    }



    bool isValidSudoku(vector<vector<char>>& board) {
        if (board.size() != 9)
            return false;



        for (int i = 0; i < 9; i++)
        {
            if (isValidArray(board[i]) == false)
                return false;
        }



        for (int i = 0; i < 9; i++)
        {
            vector<char> a;



            for (int j = 0; j < 9; j++)
            {
                a.push_back(board[j][i]);
            }



            if (isValidArray(a) == false)
                return false;
        }



        for (int i = 0; i < 9; i++)
        {
            vector<char> a;



            for (int j = 0; j < 9; j++)
            {
                a.push_back(board[(i / 3) * 3 + j / 3][(i % 3) * 3 + j % 3]);
            }



            if (isValidArray(a) == false)
                return false;
        }



        return true;
    }
};