36. Valid Sudoku - Medium

前往題目

想法

• 每行每列檢查
• 3 x 3的格子因為總數不變所以可以定位每個大格的中間格，藉此來判斷他周圍的格子

思路

不知道會不會有更好的辦法，所以看了Neetcode大大的解法，差不多，但3 x 3判斷的部分我沒想到，非常簡潔明瞭

1. 使用Set來儲存每個row、column和3 x 3格子裡 包含的數
2. 檢查所有格子，每次檢查時都檢查其行和列還有所屬3 x 3格子中是否invalid

Code

class Solution {
    public boolean isValidSudoku(char[][] board) {
        HashSet[] rows = new HashSet[9];
        HashSet[] cols = new HashSet[9];
        HashSet[][] squares = new HashSet[3][3];
        
        // Init.
        for (int i = 0; i < 9; ++i) {
            HashSet<Character> rowSet = new HashSet();
            HashSet<Character> colSet = new HashSet();
            rows[i] = rowSet;
            cols[i] = colSet;
        }

        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                HashSet<Character> squareSet = new HashSet();
                squares[i][j] = squareSet;
            }
        }

        for (int r = 0; r < 9; ++r) {
            for (int c = 0; c < 9; ++c) {
                char currCell = board[r][c];

                // Skip empty cell
                if (currCell == '.') continue;

                // Check validness
                if (rows[r].contains(currCell) ||
                    cols[c].contains(currCell) ||
                    squares[r / 3][c / 3].contains(currCell)) {
                        return false;
                }

                // Add into the set
                rows[r].add(currCell);
                cols[c].add(currCell);
                squares[r / 3][c / 3].add(currCell);
            }
        }
        return true;
    }
}

2024/04/19

• 算是簡單的一題，總之就是全部檢查就對了