36.Valid Sudoku === ###### tags: `Medium`,`Array`,`Hash Table`,`Matrix` [36. Valid Sudoku](https://leetcode.com/problems/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**: 1. Each row must contain the digits `1-9` without repetition. 2. Each column must contain the digits `1-9` without repetition. 3. 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. 白話文:就是驗證數獨。 ### 範例 ![](https://upload.wikimedia.org/wikipedia/commons/thumb/f/ff/Sudoku-by-L2G-20050714.svg/250px-Sudoku-by-L2G-20050714.svg.png) ``` 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 ``` ``` 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 `'.'`. ### 解答 #### Javascript ```javascript function isValidSudoku(board) { const block = []; for (let i = 0; i < 9; i++) { for (let j = 0; j < 9; j++) { if (board[i][j] === '.') continue; // 檢查橫的跟直的 for (let k = 0; k < 9; k++) { if (board[i][k] === board[i][j] && k !== j) return false; if (board[k][j] === board[i][j] && k !== i) return false; } // 檢查九宮格 const blockIndex = ~~(i / 3) * 3 + ~~(j / 3); if (!block[blockIndex]) block[blockIndex] = []; for (let k = 0; k < block[blockIndex].length; k++) { if (block[blockIndex][k] === board[i][j]) return false; } block[blockIndex].push(board[i][j]); } } return true; } ``` > [name=Marsgoat] [time= Nov 23, 2022] #### C++ ```cpp bool isValidSudoku(vector<vector<char>>& board) { unordered_map<int,unordered_set<char>> horizon_appear; unordered_map<int,unordered_set<char>> vertical_appear; unordered_map<int,unordered_set<char>> block_appear; int row_n = board.size(), col_n = board[0].size(); for(int row = 0; row < row_n; row++) { for(int col = 0; col < col_n; col++) { char cur = board[row][col]; if(cur == '.') continue; if(horizon_appear.count(row) && horizon_appear[row].count(cur)) return false; if(vertical_appear.count(col) && vertical_appear[col].count(cur)) return false; if(block_appear.count((col/3)*3+row/3) && block_appear[(col/3)*3+row/3].count(cur)) return false; horizon_appear[row].insert(cur); vertical_appear[col].insert(cur); block_appear[(col/3)*3+row/3].insert(cur); } } return true; } ``` Time: $O(N^2)$ Space: $O(N^2)$ 更少的Space: $O(N)$ 可以更換map成`vector<int> rows(N), cols(N), squares(N);` 用int儲存bitmask, 第i個位置代表數字i有無出現 [Reference](https://leetcode.com/problems/valid-sudoku/discuss/1414911/C%2B%2BJavaPython-2-solutions%3A-HashSet-Bitmasking-Clean-and-Concise-O(49)) > [name=XD] [time= Nov 23, 2022] ### Reference [回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)