Topic describes

Here’s 36 valid Sudoku on LeetCode, Medium difficulty.

Determine if a 9×9 sudoku is valid. You only need to verify that the numbers you have entered are valid according to the following rules.

  • The numbers 1-9 can appear only once in each line.
  • The numbers 1-9 May appear only once in each column.
  • The numbers 1-9 can occur only once in each 3×3 palace separated by a thick solid line.

Above is a partially filled valid sudoku.

Numbers have been filled in the blank space of sudoku, and the blank space is represented by ‘.’.

Example 1:

Input: [[" 5 ", "3", ""," ", "7", ""," ", ""," "], [" 6 ", ""," ", "1", "9", "5", ""," ", ""], [".", "9", "eight" and ". ", ""," ", ""," 6 ", ""]. [" 8 "and". ", ""," ", "6", ""," ", ""," 3 "], [" 4 ", ""," ", "eight" and ". ", "3", ""," ", "1"], [" 7 ", ""," ", ""," 2 ", ""," ", ""," 6 "]. [". ", "6", ""," ", ""," ", "2", "eight", ""], [".", ""," ", "4", "1", "9", ""," ", "5"]. [".",".","."," 8","."," 7","9"]] output: trueCopy the code

Example 2:

Input: [[" 8 ", "3", ""," ", "7", ""," ", ""," "], [" 6 ", ""," ", "1", "9", "5", ""," ", ""], [".", "9", "eight" and ". ", ""," ", ""," 6 ", ""]. [" 8 "and". ", ""," ", "6", ""," ", ""," 3 "], [" 4 ", ""," ", "eight" and ". ", "3", ""," ", "1"], [" 7 ", ""," ", ""," 2 ", ""," ", ""," 6 "]. [". ", "6", ""," ", ""," ", "2", "eight", ""], [".", ""," ", "4", "1", "9", ""," ", "5"]. [". ", ". ", ""," ", "eight" and ". ", ""," 7 ", "9"]] output: false interpretation: in addition to the first line of the first number changed from 5 to 8, the Spaces within the other Numbers are the same as the sample 1. But since there are two eights in the 3x3 in the upper left corner, this sudoku is invalid.Copy the code

Description:

  • A valid sudoku (partially filled) is not necessarily solvable.
  • You only need to verify that the entered numbers are valid according to the above rules.
  • Given sudoku sequences contain only the numbers 1-9 and the characters ‘.’.
  • Sudoku is always 9×9.

Hash table solution

As long as we judge whether it is valid for sudoku.

So we only need to judge the number in the board. If there are several numbers in the board that violate the rules of Sudoku, return false, otherwise return true.

Intuitively, it’s easy to think of using a hash table to record which numbers appear in a row/column/square to help us determine if we meet the definition of “valid Sudoku.”

The only difficulty in this problem may be how to determine which cube a certain number falls in. We can number the cube:

Then the relation between the number of small squares and the row and column is deduced: IDx = I / 3 * 3 + J / 3.

class Solution {
    public boolean isValidSudoku(char[][] board) {
        Map<Integer, Set<Integer>> row  = new HashMap<>(), col = new HashMap<>(), area = new HashMap<>();
        for (int i = 0; i < 9; i++) {
            row.put(i, new HashSet<>());
            col.put(i, new HashSet<>());
            area.put(i, new HashSet<>());
        }
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '. ') continue;
                int c = board[i][j] - '1';
                int idx = i / 3 * 3 + j / 3;
                if(! row.get(i).contains(c) && ! col.get(j).contains(c) && ! area.get(idx).contains(c)) { row.get(i).add(c); col.get(j).add(c); area.get(idx).add(c); }else {
                    return false; }}}return true; }}Copy the code
  • Time complexity: fixed9 * 9Where complexity does not vary with data. Complexity of
    O ( 1 ) O(1)
  • Space complexity: fixed9 * 9Where complexity does not vary with data. Complexity of
    O ( 1 ) O(1)

An array of solutions

Most hash table counting problems can be converted to arrays.

Although time complexity, but the updating and query complexity of the hash table is an average of O (1) O (1) O (1), and fixed length of the array of the update, and query complexity is strictly O (1) O (1) O (1).

Arrays are therefore much faster than hash tables in terms of execution efficiency:

class Solution {
    public boolean isValidSudoku(char[][] board) {
        boolean[][] row = new boolean[9] [9], col = new boolean[9] [9], area = new boolean[9] [9];        
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '. ') continue;
                int c = board[i][j] - '1';
                int idx = i / 3 * 3 + j / 3;
                if(! row[i][c] && ! col[j][c] && ! area[idx][c]) { row[i][c] = col[j][c] = area[idx][c] =true;
                } else {
                    return false; }}}return true; }}Copy the code
  • Time complexity: fixed9 * 9Where complexity does not vary with data. Complexity of
    O ( 1 ) O(1)
  • Space complexity: fixed9 * 9Where complexity does not vary with data. Complexity of
    O ( 1 ) O(1)

The last

This is the 36th article in our “Brush through LeetCode” series. The series started on 2021/01/01. There are 1916 questions on LeetCode by the start date, some of which have locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.

  • This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign