Interview Classic 150 Questions P36 Valid Sudoku

---

Timeline

Timeline

2025-11-14

init

Matrix

---

Problem:

P36 Valid Sudoku

https://leetcode.cn/problems/valid-sudoku/description/?envType=study-plan-v2&envId=top-interview-150

Just compare directly without overthinking

#include <vector>
#include <unordered_set>

using std::vector;
using std::unordered_set;

#define BOARD_LENGTH 9
#define SMALL_BOARD_LENGTH 3
class Solution {
    public:
	bool judge(vector<vector<char> > &board, int start_i, int start_j, int sn)
	{
		unordered_set<char> uset;
		int i, j;
		for (i = start_i; i < start_i + sn; i++) {
			for (j = start_j; j < start_j + sn; j++) {
				if (board[i][j] == '.') {
					continue;
				}
				if (uset.count(board[i][j])) {
					return false;
				}
				uset.insert(board[i][j]);
			}
		}
		return true;
	}
	bool isValidSudoku(vector<vector<char> > &board)
	{
		// 9*9
		int i, j;
		int n = BOARD_LENGTH;
		int sn = SMALL_BOARD_LENGTH;
		// All elements in each row must appear only once

		for (i = 0; i < n; i++) {
			unordered_set<char> uset;
			for (j = 0; j < n; j++) {
				if (board[i][j] == '.') { //Do not count blank cells
					continue;
				}
				if (uset.count(board[i][j])) {
					return false;
				}
				uset.insert(board[i][j]);
			}
		}
		//All elements in each column must appear only once
		for (j = 0; j < n; j++) {
			unordered_set<char> uset;
			for (i = 0; i < n; i++) {
				if (board[i][j] == '.') {
					continue;
				}
				if (uset.count(board[i][j])) {
					return false;
				}
				uset.insert(board[i][j]);
			}
		}
		// Each 3x3 sub-box must have each number appear only once
		for (i = 0; i < n; i += sn) {
			for (j = 0; j < n; j += sn) {
				if (!judge(board, i, j, sn)) {
					return false;
				}
			}
		}
		return true;
	}
};