Leetcode Study Day 16

Valid Sudoku

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.
Note:

A Sudoku board (partially filled) could be valid but is not necessarily solvable.
Only the filled cells need to be validated according to the mentioned rules.

Example 1:


Input: board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: true
Example 2:

Input: board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.
 

Constraints:

board.length == 9
board[i].length == 9
board[i][j] is a digit 1-9 or '.'.

Solution

This solution is found in the Leetcode discussion board. His idea is to iterate all the elements in the board, and insert this element’s horizontal, vertical and grid information into a set. If the set already contains this element, we return false. Otherwise, we continue the iteration. If the iteration is finished, we return true.

class Solution {
public:

bool isValidSudoku(vector<vector<char>>& board) {
    set<string> seen;
    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            char number = board[i][j];
            if (number != '.') {
                // Construct the unique strings for row, column, and block checks
                // We use std::string(1, number) to create a single-character string from the char number.
                string rowStr = string(1, number) + " in row " + to_string(i);
                string colStr = string(1, number) + " in column " + to_string(j);
                string blockStr = string(1, number) + " in block " + to_string(i / 3) + "-" + to_string(j / 3);
                
                // Check if any of the strings already exist in the set
                if (!seen.insert(rowStr).second || 
                    !seen.insert(colStr).second || 
                    !seen.insert(blockStr).second)
                    return false;
            }
        }
    }
    return true;
}
};